KMP算法

把之前的kmp博客删了，现在重新写一下kmp

暴力字符串的匹配

假设给两个字符串s和p，要求查询s是否在p中出现过，那么该如何进行进行实现呢？ 朴素的想法是从每次枚举p在s中的开始位置然后开始暴力向后匹配，每次匹配失败后就直接从下一个s的位置开始继续匹配。 这种做法很容易想到，但是仔细一算就可以发现很耗时。

假设s和p分别长为n和m那么这样匹配最差情况下大概是$O(n\ast m)$级别。

KMP字符串匹配

KMP匹配实际上是对暴力匹配的改进。 假设P在和S匹配时匹配失败了(在下图蓝色后面处匹配失败) 那么此时p串就需要往后移动，那么p究竟最多可以移动多远才能再次匹配呢？ 假设P移动到了P’位置再次与S匹配了 那么就可以很自然的发现一个相等条件，由于匹配三段绿色的部分F1,F2,F3很自然的就相等 同时F3又等于灰色的G1 所以很神奇地，最终得到F2等于G1，也就是P自身在匹配失败的前一个位置处存在一个子串和P的前缀相等。 此时观察D点，可以发现其实就是D’点 假设在$i$和$j$为两个分别匹配S和P的指针，假设在$i$和$j$处匹配失败。 那么此时$j$指针就可以移动到D处 道理很简单因为G1等于F3而F3已经被匹配过了，所以只需要从D处继续匹配就可以了。 到此为止KMP的思想你已经学会了。

求next数组

在上面的分析中，有一个D点这个D点是在匹配失败后$j$指针回到得到地方，所以可以设置这么一个数组nex，表示nex[i]等于回到上述D点的位置。

上面的这种数组可以用一下代码实现，这段代码可以自己模拟一下，就可以明白了

for(int i = 2, j = 0; i <= len2; i++){//len2表示p的长度 while(j && p[j + 1] != p[i])j = nex[j];//假设j匹配失败，就回到上一个D点 if(p[j + 1] == p[i])j++;//如果成功就加一 nex[i] = j; }

KMP全过程

const int maxn = 1e6 + 5; char p[maxn],s[maxn]; ll n,m,nex[maxn]; int main(){ scanf("%s", s + 1), scanf("%s", p + 1); int len1 = strlen(s + 1),len2 = strlen(p + 1); for(int i = 2, j = 0; i <= len2; i++){ while(j && p[j + 1] != p[i])j = nex[j]; if(p[j + 1] == p[i])j++; nex[i] = j; } for(int i = 1, j = 0; i <= len1; i++){ while(j && p[j + 1] != s[i])j = nex[j];//如果不匹配就回到nex，知道回到头或者重新匹配的位置 if(p[j + 1] == s[i])j++;//如果匹配就加一 if(j == len2){//j匹配到len2时就匹配成功 printf("%d\n", i - len2 + 1);//输出这个子串的位置 j = nex[j];//回到上次匹配的地方继续 } } return 0; }