基本思路

• KMP算法的本质是朴素模式匹配算法的优化，当模式串和主串当前字符匹配失败后，不必将主串回溯，而是根据模式串的特征，将模式串缩减，继续与主串进行比较，而模式串的这种特征存储在next数组内，KMP算法的关键就在于求next数组。
• next数组的值，即当模式串与主串字符匹配失败后，模式串的角标应设定的值。
• 对于next[n]，数值上等于字符串str[0,n-1]的前缀和后缀的最大相同区域的长度。
• 换言之，str[0,n-1]的前next[n]个字符与str[0,n-1]的后next[n]个字符完全相同，所以只需将模式串的第next[n]+1个字符，也即str[next[n]]，与主串当前字符进行比较即可。
• 当next[n]为0时，说明字符串str[0,n-1]没有相同的前缀和后缀，只能用str[0]与主串当前字符作比较；若str[0]也与主串当前字符串不符合，我们只好去访问主串的下一个字符，为了标记这个特殊情况，我们把next[0]设为-1。
• 求next数组时也用到了KMP算法的思想，对于next[i+1]，将str[0,i]视为主串，将其前缀str[0,j]视为模式串，当在主串的后缀处匹配到模式串，我们就找到了str[0,i]的前缀和后缀的一个相同区域。
• 那么如何保证这个相同区域是最大的，由于next[i+1]<=next[i]+1，我们只需设一个变量j，令其的初始值为next[i]，而且我们知道str[0,i-1]的后缀与str[0,j-1]相同。
• 若str[j]==str[i]，str[0,i]的后缀就与str[0,j]完全相同，则next[i+1]为最大值next[i]+1，也即next[i+1]=j+1。
• 若str[i] ! =str[j]，根据KMP算法的思想以及next数组的性质，令j=next[j]将模式串str[0,j]进行缩减，再与主串str[0,i]的后缀比较，以此类推。
• 构造next数组以及KMP查找字符串，都是在缩减模式串，在构造next数组时，如若模式串str[0,j]完全缩减，也即j==-1，认为主串str[0,i]的前缀和后缀没有相同区域，next数组的值为0。
• 在用KMP算法查找字符串时，模式串从一个字符逐渐扩充，直到完全匹配；当模式串当前字符与主串当前字符匹配失败，就会根据next数组缩减模式串，如若模式串str完全缩减，即j==-1，说明模式串没有前缀能和主串的当前片段所匹配，只能访问主串的下一字符。
• 当str[n]==str[next[n]]，主串的当前字符与str[next[n]]的比较结果一定不同，next数组可进一步优化，令next[n]的值为next[next[n]]，减少了KMP算法的比较次数。

代码实现

#include
#include//求next数组
void get_next(char* str, int* next)
{	//str[i]为“主串”str[0,i]的尾端//str[j]为“模式串”str[0,j]的尾端int i = 0;  int j = -1; //next[0]特殊处理next[0] = -1;//为next[i+1]赋值while (i + 1 < strlen(str)){//j==-1说明没有相同区域，next[i+1]=0//str[i]==str[j]说明找到了最大的相同区域if (j == -1 || str[i] == str[j]){next[++i] = ++j;//优化next数组while (str[i] == str[next[i]])next[i] = next[next[i]];}else//缩减模式串j = next[j];}
}//KMP算法，返回值为模式串首次出现的角标
int KMP(char* S, char* str)
{int i = 0, j = 0;//构造next数组int next[10];get_next(str, next);printf("\n");//strlen的返回值是无符号型，需要转换成有符号型才能和-1进行比较while (i < (int)strlen(S) && j < (int)strlen(str)){//j==-1说明需要重置模式串，并访问主串的下一个字符//S[i]==str[j]说明当前字符匹配成功，进行下一个字符的比较if (j == -1 || S[i] == str[j]){i++;j++;}else//缩减模式串j = next[j];}//模式串匹配完毕if (j == strlen(str))//返回子串角标return i - j;elsereturn -1;
}int main()
{//定义3个主串char S[5][20] = {"ababaacdef" ,"abababaacdef","babababaacdef","aabaabaaacadaef","bbaabaababaacdef"};//定义模式串char str[] = "ababaa";//进行KMP匹配for (int i = 0; i < 5; i++){int n = KMP(S[i], str);if (n != -1){printf("模式串在主串中的角标为%d\n", n);printf("自此向后的内容为：%s\n", S[i] + n);}elseprintf("主串中不存在该模式串\n");printf("\n");}return 0;
}