https://blog.csdn.net/qq_33375598/article/details/104479391
@[toc]
1 next数组
1.1 概念
假设有一个字符串s（下标从0开始），那么它以i号位结尾的子串就是s[0...i]。对于该子串来说，长度为k+1的前缀和和后缀和分别为s[0...k]和s[i-k...i]。
现定一个一个int型数组next，
- next[i]表示：使子串s[0...i]的前缀和s[0...k]等于后缀和[i-k...i]的最大k（==前缀和和后缀和可以重叠，但不能是s[0...i]本身==）；如果找不到相等的前后缀和，那么就令next[i] = -1。
- 显然，next[i]就是所求最长相等前后缀和中前缀最后一位的下标。
1.2 暴力求解next数组
以字符串s = “ababaab”为例子，next数组的计算过程如下图所示：
图中，上框直接用下划线画出了子串s[0...i]的最长相等前后缀和，而下框将子串s[0...i]写成两行，让第一行提供后缀，第二行提供*前缀，然后将相等的前后缀框起来。 - 1 当i=0：子串s[0..i]为“a”，由于找不到相同的前后缀和（前后缀均不能是字符串本身，下同），令next[0] = -1;
- 2 当i=1：子串s[0..i]为“ab”，由于找不到相同的前后缀和），令next[1] = -1;
- 2 当i=2：子串s[0..i]为“aba”，能使前后缀相等的最大k为0，此时后缀s[i-k...i]为“a”，前缀s[0...k]也为“a”，而当k=1，后缀s[i-k...i]为“ba”，前缀s[0...k]也为“ab”，它们不相等。令next[2] = 0;
- 3 当i=3：子串s[0..i]为“abab”，能使前后缀相等的最大k为1，此时后缀s[i-k...i]为“a”，前缀s[0...k]也为“a”，而当k=2，后缀s[i-k...i]为“bab”，前缀s[0...k]也为“aba”，它们不相等。令next[3] = 1;
- 4 当i=3：子串s[0..i]为“abab”，能使前后缀相等的最大k为1，此时后缀s[i-k...i]为“a”，前缀s[0...k]也为“a”，而当k=2，后缀s[i-k...i]为“bab”，前缀s[0...k]也为“aba”，它们不相等。令next[3] = 1;
- 5 当i=4：子串s[0..i]为“ababa”，能使前后缀相等的最大k为2，此时后缀s[i-k...i]为“aba”，前缀s[0...k]也为“aba”，而当k=3，后缀s[i-k...i]为“baba”，前缀s[0...k]也为“abab”，它们不相等。令next[4] = 2;
- 6 当i=5：子串s[0..i]为“ababaa”，能使前后缀相等的最大k为0，此时后缀s[i-k...i]为“a”，前缀s[0...k]也为“a”，而当k=1，后缀s[i-k...i]为“aa”，前缀s[0...k]也为“ab”，它们不相等。令next[5] = 0;
- 7 当i=6：子串s[0..i]为“ababaab”，能使前后缀相等的最大k为1，此时后缀s[i-k...i]为“ab”，前缀s[0...k]也为“ab”，而当k=2，后缀s[i-k...i]为“aab”，前缀s[0...k]也为“aba”，它们不相等。令next[6] = 1，
==由此可以得出next[i]就是子串s[0...i]的最长相等前后缀的前缀最后一位的下标。==
1.3 递推求解next数组
暴力求解next数组显然不够高效，下面用递推的方法高效求next数组。
还是以以字符串s = “ababaab”为例子。
假设已经求得next[0] = -1, next[1] = -1, next[2] = 0, next[3] = 1,
现在来求next[4]，
如上图所示，当已经得到next[3] = 1时，最长相等前后缀为"ab",在计算next[4]时，由于s[4] == s[next[3]+1],因此可以把最长相等前后"ab"扩展为“aba”,因此next[4] =next[3] +1 = 2，并令j指向next[4]。
现在求next[5],
如上图所示，当已经得到next[4] = 2时，最长相等前后缀为"aba"，计算next[5],由于s[5] != s[next[4]+1]，因此不能扩展最长相等前后缀。
现在我们可以缩短一点，寻找一个j使得s[5] = s[j+1],（图中的波浪线～表示s[0...j]），为了找到相等的前后缀和尽可能长，找到的这个j应尽可能的大。
实际上在要求既是S[0..2] (s[0...j]) = "aba"前缀，也是S[0..2] = "aba"的后缀，同时有希望长度尽量长。只需令j= next[2],然后在判断s[5] == s[j+1]是否成立，如果成立，说明s[0..j+1]是s[0...5]最长前后缀，令nex[5] = j+1即可，如果不成立，不断的让j= next[j],直到j回到了-1，或者中途s[5] = s[j+1]成立。
由于j已经退到了-1，因此不能在继续退，但是发现了s[i] = s[j+1]成立,说明s[0...j+1]是s[0..5]的最长相等前后缀和，就令next[5] = j+1= -1+1= 0,并令j指向next[5]。如下图所示：
由上面例子可以发现，每次求完next[i]后，都令j指向next[i]。
1.3.1 总结思路
- 1初始化next数组，令j=next[0]= -1;
- 2 让i在1～len-1 范围遍历，对于每个i执行3、4，以求解next数组；
- 3 不断的令j = next[j],直到回退到-1，或者s[i] == s[j+1]成立；
- 4 如果s[i] == j+1,则next[i] = j+1,否则next[i] = j。
1.3.2 模版代码
//求解长度为len的字符串s的snext数组
void getNext(char s[],int len){
//初始化
int j = -1;
next[0] = -1;
for (int i = 1; i < len; ++i)
{
while(j != -1 && s[i] != s[j + 1]){
j = next[j];//反复令j等于next[j]
}//直到j回退到-1或是s[i] = s[j+1]
if(s[i] == s[j + 1]){//如果s[i] = s[j+1]
j++;//则next[i] = j+1;先令j指向这个位置
}
next[i] = j;
}
} 2 KMP
2.1 概念
给出两个字符串text和pattern，需要判断字符串pattern是否是字符串text的子串。一般把字符串text称为文本串，而把字符串pattern称为模式串。
2.2 暴力求解 O(nm)
只要枚举文本串的位置i，然后从该位置开始逐位与模式串进行匹配，如果匹配过程中每一位都相同，则匹配成功，否则，只要某位出现不同，就让文本串的位置变为i+1,并且从头开始模式串匹配。这种做法的时间复杂度为O（mn）,n和m分别为文本串和模式串的长度。
2.3 KMP O(n+m)
2.3.1 思想
时间复杂度O(n+m)，n和m分别为文本串和模式串的长度。
以text="abababaabc"，pattern="ababaab"为例子。
令i指向text当前欲比较位置，j指向pattern中当前已被匹配的最后位置，
- 这样只要text[i] = pattern[j+1] ，就说明pattern[j+1]也被成功匹配，此时让i、j加1继续比较，直到j到达m-1时，说明pattern是text的子串（m为模式串的长度）
如上图所示，左图说明i指向text[4],j指向pattern[3],说明pattern[0...3]已经全部匹配成功，此时发现text[i] = pattern[j+1]成立，说明pattern[4]成功匹配，于是令i、j加1。
如上图所示，i指向5，说明pattern[0...4]已经全部匹配成功，于是判断text[i] ==pattern[j+1]是否成功。但此时text[i] != pattern[j+1],匹配失败，需要让j会到-1重新开始匹配吗？当然不是。
此时应该寻求退回一个里j最近的j',使得text[i] = pattern[1+j']能够成立，并且pattern[0...j']仍与text相应位置处于匹配状态，即pattern[0...j']就是pattren[0...j]的最长相等前后缀。（==pattern为前缀，text为后缀==）
此时不断令j=next[j],直到j回退到-1或者text[i] = pattren[j+1]成立，然后继续匹配继续。
从这个角度说，next数组就是当j+1位匹配失败时，j应该回退的位置
当text[5]和pattern[5]匹配失败时，令j=next[4] = 2，然后就会惊讶的发现text[i] == pattern[j+1] 能够成立，因此就让它继续匹配，直到j==6匹配成功。，就意味着pattern是text的子串。
2.3.2 模版思路
- 1初始化j = -1,表示pattern当前已被匹配的最后位置；
- 2 让i（当前text欲比较的位置）遍历文本串，对每个i，执行3、4来试图匹配text[i]和pattern[j+1];
- 3 不断令j = next[j],直到j回退到-1，或是text[i] == pattern[j+1]成立；
- 4 如果text[i] == pattern[j+1],则令j++。如果j达到m-1，说明pattrenhitext的子串，返回true。
2.3.3 模版代码
//判断pattren是否是text的子串
bool KMP(char text[], char pattern[]){
int n = strlen(text), m = strlen(pattern);//字符串的长度
getNext(pattern, m);//计算pattern的next数组
int j = -1;//初始化位-1，表示当前还没有任意一位被匹配
for (int i = 0; i < n; ++i)
{
while(j != -1 && text[i] != pattern[j + 1]){//试图匹配text[i]
j = next[j];//不断回退，直到j会到-1或者text[i] == pattern[j + 1]
}
if(text[i] == pattern[j + 1]){
j++;//text[i] 与pattern[j+1]匹配成功，令j加1
}
if(j == m - 1){//pattern完全匹配，说明pattern是text的子串
return true;
}
}
return true;
} 观察代码，发现求解next数组的过程就是模式串pattern进行自我匹配的过程。
2.3.4 统计模式串在文本串出现的次数
2.3.4.1 思想
例如在文本串text="abababab"来说，模式串pattern=“abab”出现了三次，而模式串“ababa"出现了两次。
当j=m-1表示一次成功的完全匹配，此时可以令记录成功匹配次数的变量加1，但问题在于下次从pattern的哪一个位置进行匹配？
如果直接让i+1进行下一次的匹配，会出现错误。因为模式串pattern在文本串text的多次出现可能是重叠的。
此时可以让j回退的next[j]（next[j]代表整个模式串pattern的最长相等前后缀），即让已经成功匹配的部分最长，这样能保证就不漏解，又让下一次的匹配省去许多无意义的比较。
2.3.4.2 实现代码
//判断pattren是text的子串的次数
int KMP(char text[], char pattern[]){
int n = strlen(text), m = strlen(pattern);//字符串的长度
getNext(pattern, m);//计算pattern的next数组
int j = -1;//初始化位-1，表示当前还没有任意一位被匹配
int ans = 0;//表示成功匹配的次数
for (int i = 0; i < n; ++i)
{
while(j != -1 && text[i] != pattern[j + 1]){//试图匹配text[i]
j = next[j];//不断回退，直到j会到-1或者text[i] == pattern[j + 1]
}
if(text[i] == pattern[j + 1]){
j++;//text[i] 与pattern[j+1]匹配成功，令j加1
}
if(j == m - 1){//pattern完全匹配，说明pattern是text的子串
ans++;//成功匹配次数加1
j = next[j];//让j会到next[j]继续匹配
}
}
return ans;
} 2.3.4.3 时间复杂度计算
整个for循环中i不断加1，所以在整个过程中i的变化次数是O（n）级别；
接下来考虑j，j只会在一行中增加，且每次只会加1，所以整个过程中j最多只加n次；
而其他地方的j都是不断减小的，而最小不会小于-1，因此整个过程中j最多只能减少n次，也就是while循环最多只会执行n次，因此j在整个过程中变化次数是O(n)级别（可以认为均摊到每cifor循环中，就是O(1)）。
i和j在整个过程中的变化次数都是O（n），因此for循环部分的整个时间复杂度就是O(n)。以同样的方法分析求next数组的函数getNext（）所用的时间复杂度为O(m),因此总的时间复杂度为O(n+m)。
2.4 nextval数组
2.4.1 概念
模式串"ababab"去匹配文本串“ababacab”，其中试图匹配‘c’的过程如下图所示：
上图中，一开始i=5，j=4，因此text[i] = 'c',pattern[j+1] = 'b',它们不匹配；于是j回退到next[4] = 2,发现pattern[j+1]还是‘b’，还是不匹配；于是j回退到next[2] = 0，此时又有pattern[j+1]还是‘b’，毫无疑问肯定还是不匹配；最后j回退到next[0] = -1，此时终于出现patterm[j+1]不是‘b’了，可以和text[i]比较了。
显然，在第一次text[i]和'b'匹配失败后，接下来的一连串'b'必然失配的，要是想办法直接跳过跳过这些‘b’，一定提高效率。
从匹配角度看,next[j]表示当模式串j+1失配时，j应该回退到的位置。j进行无意义回退的问题出现pattern[j+1] = pattern[next[j] + 1]上。就上面的例子来说，当j=4时，pattern[j+1]= 'b',将失配回退到next[j] = 2,显然pattern[next[j] +1] = pattern[3] = 'b',因此pattern[j+1] == pattern[next[j]+1]成立，这次回退没有意义。
可以想到，如果让j继续回退，变成next[next[j]],然后看pattern[next[j]+1] == pattern[next[next[j]]+1]是否成立，如果成立，说明还需继续后退，这样实际上还是会做许多无意义的后退。
解决办法在于在求解next数组过程的基础上做修改即可。观察求next的程序可得，在最后的语句"next[i] = j"之前，j已经指向原先意义的next[i]的位置，需要在这里判断，
- 如果有pattern[i+1]!= pattern[j+1]成立（即pattern[i + 1] != pattern[next[i] +1]）(这里的i是对模式串pattern来说)，则说明不需要回退，按原先的写法next[i] = j即可；
- 如果 pattern[i+1]==pattern[j + 1]成立的化，则说明需要回退，令next[i]继承next[j]。
对例题来说，已知模式串“ababab”,已知next[0],在求解next[2]时，它会继承next[0]的结果得到next[2] = -1,在求解next[4]时，又会继承next[2]的结果得到next[4] = -1。
此时优化后的next数组又称为nextval数组，它丢失了next数组最长相等前后缀的含义，却让匹配得到最优。
==此时nextval[i]的含义为：当前模式串pattern[i]的i+1位发生失配时，i应当回退到的最佳位置。==
2.4.2 模版代码
//求解长度为len的字符串s的nextval数组
void getNextval(char s[], int len){
int j = -1;
nextval[0] = -1;
for (int i = 1; i < len; ++i)
{
while(j != -1 && s[i] != s[j+1]){//求解nextval[1]~nextval[len-1]
j = nextval[j];
} //直接回退到-1，或是s[i] == s[j+1]
if(s[i] == s[j+1]){//s[i] == s[j+1]
j++;//令j指向next[i]的位置
}
//下面与getNext()不同
if(j == -1 || s[i + 1] != s[j + 1]){//j==-1不需要回退
nextval[i] = j;//getNext只有这一句
}else{
nextval[i] = nextval[j];
}
}
} 思考：
- 为什么s[i+1] != s[j+1]的判断不需要加上i<len的条件。因为从nextval的角度上说，如果i已经是模式串pattern的最后一位，那么i+1失配的说法从匹配的角度上说没有意义（由于s[len]是'\0'，且j一定小于i（原因：本身不能是最大前后缀和），因此一定会失配），也就是说nextval[len-1]可有可无，它在KMP中一定不会被用到。
- 由于nextval数组的含义，getNextVal和KMP中while都可以替换为if，因为最多执行一次。
3 从有限状态自动机（AC自动机）看KMP
通俗来讲，可以把有限状态机看作一个有向图，其中顶点表示不同的状态（类似于动态规划中的状态），边表示状态之间的转移。有限状态机有一个起始状态和终止状态，从起始状态出发，最终转移到终止状态，那状态机就会正常停止。
对KMP算法来讲，就相当于对模式串pattern构造一个有限状态机，然后将文本串text的字符从头到尾一个一个送入这个机器，如果自动机可以从初始状态到达最终状态，那么说明pattern是text的子串。
如上图所示，起始状态是0，终止状态是6。如果在状态0，输入字符‘a’，就会进入状态1，如果在状态1，输入字符‘b’，就会进入状态2，如果文本串中有"ababab"这个子串，状态就会不断的从0转移到6，自动机就成功停止了。
如果图中碰到了意外情况，例如在状态4送入自动机的不是‘a’，它就沿一条回退的边转移到转台2 。如果初始状态0，送入自动机的不是字符‘a’，它就会从一条自己转移到自己的边绕圈，这样自动机就会一直处于初始状态。
图中所有回退箭头就是next数组代表的位置，其中-1和0和统一合并为起始位置。
现在来计算文本串中“abababab”中有多少个模式串"ababab"。起始时状态处于0，然后将字符‘a’送入自动机，状态转移为1，直到第六位字符‘b’送入自动机，使状态达到6，表示模式串在文本串中完整出现过一次。
接着状态由箭头转移到状态4继续匹配。此时文本串第7位为‘a’，状态转移到状态5，最后文本串第8位为‘b’，使状态转移到状态6，表示模式串"ababab"完整的出现两次。
这正是KMP算法的流程，十分简明。
如果把这个自动机推广为树形，就产生字典树（前缀树），可以解决***字符串匹配问题（即一个文本匹配多个模式串使得匹配问题）。
通常把解决***字符串匹配问题的算法称为AC自动机。
而KMP算法只不过是AC自动机的特殊形式。
京公网安备 11010502036488号