KMP算法求next数组的问题
2.利用上题p=”aabcaabbaa”优化后的Next数组，对t=”aaabaabcabaabcaabbaab”进行匹配。有多少次字符比较？ 展开
字符串如果是以0为下标的话next[7]是0，只有最后一位与第一位相等。
在第i个字符前面的i-1个字符里面，
从开头开始的1个字符与最后1个字符是否相等，若不是，则next[i]=0；
从开头开始的2个字符与最后2个字符是否相等，若不是，则next[i]=1；
从开头开始的3个字符与最后3个字符是否相等，若不是，则next[i]=2；
前缀next数组的求解算法：
void SetPrefix(const char *Pattern, int prefix[])
{
int len=CharLen(Pattern);//模式字符串长度。
prefix[0]=0;
for(int i=1; i<len; i++)
{
int k=prefix[i-1];
//不断递归判断是否存在子对称，k=0说明不再有子对称，Pattern[i] != Pattern[k]说明虽然对称，但是对称后面的值和当前的字符值不相等，所以继续递推。
扩展资料：
kmp算法完成的任务是：给定两个字符串O和f，长度分别为n和m，判断f是否在O中出现，如果出现则返回出现的位置。常规方法是遍历a的每一个位置，然后从该位置开始和b进行匹配，但是这种方法的复杂度是O(nm)。kmp算法通过一个O(m)的预处理，使匹配的复杂度降为O(n+m)。
参考资料来源：百度百科-简约KMP算法
KMP算法，主要分为2个阶段：
求next数组。
字符串匹配
next数组，就是对给定的“匹配字符串”，求出其每一个子长度字串的“最长前缀和最长后缀相等的长度”。
匹配串，p="aabcaabbaa", 长度n=10。因此子串为sub[10]：
sub[0] = "a"
sub[1] = "aa"
sub[2] = "aab"
sub[3] = "aabc"
sub[4] = "aabca"
sub[5] = "aabcaa"
sub[6] = "aabcaab"
sub[7] = "aabcaabb"
sub[8] = "aabcaabba"
sub[9] = "aabcaabbaa"
根据“最长前缀和最长后缀相等的长度”，可以求出对应的next数组是：
next[0] = -1; // "a"
next[1] = 0; // "aa"
next[2] = -1; // "aab"
next[3] = -1; // "aabc"
next[4] = 0; // "aabca"
next[5] = 1; // "aabcaa"
next[6] = -1; // "aabcaab"
next[7] = -1; // "aabcaabb"
next[8] = 0; // "aabcaabba"
next[9] = 1; // "aabcaabbaa"
2. 利用上部求出的next数组，对t和p进行匹配。要点是：
（1）循环匹配
（2）如果整个匹配上，则返回匹配位置。
（3）如果当前位置没有匹配上，则：如果对应next[x]为-1，则跳过整个p的长度；否则，回溯到其前缀位置进行匹配。匹配上，则右移next[x-1]位置；否则，右移next[x]位置。
具体到“多少次字符匹配”，在编制的程序里加上统计的语句，最后输出。真要一个个字符统计，很容易出错。
有问题继续交流，谢谢。
