作用：算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数/ 失配数组 实现，函数本身包含了模式串的局部匹配信息。
时间复杂度：O(m+n)
核心：失配数组
1）最长公共前后缀作用：
eg: 文本串s abeabeabf
模式串s1 abeabf
如上两串匹配到画线部分时会失配
普通匹配会倒退主串到s[2],即b位置，然后重新匹配串s1,如果不倒退直接往前呢？那是不行的（考虑该情况 s: aaaab s1: aaab）
而观察到两串已匹配且未失配的部分，其最长公共前后缀为ab，即文本串能重新与模式串进行匹配、文本串涵盖有模式串前缀的地方即后缀所在处，只有这一处是两串有可能匹配成功的且长度最长的，所以可以直接将模式串的前缀ab移动到后缀ab处，文本串不动，继续匹配
2）含义：next[i]表示串s 0~i-1部分的公共最长前后缀，进行一点优化（当s[j]==s[k],将 next[j]=k 变为 next[j]=next[k]）
3）作用：记录好匹配过的部分的状态，使失配时主串不需要回退，只需利用nex记录移动更新nex数组的位置，避免重复匹配，达到快速匹配。
4）优化
优化前：
1 while(j<len){ 2 if(k==-1||s[j]==s[k]) 3 ++j,++k,nex[j]=k; //nex[i]等于i前最长公共前后缀，记录好匹配过的状态 4 else k=nex[k]; 5 }
优化后：
eg: 文本串s aabcabe
模式串s1 abcabd 字串匹配到s1串的d和s串的e处失配，为继续下一步匹配，调用d的nex，即nex[6]=3,因为d前面部分与模式串相同的字符截止到c，
模式串s2 abcabc 字串匹配到s2串的d和s串的e处失配，为继续下一步匹配，调用c的nex，此时nex[6]=0，即失配此时并未失配，若nex[6]=3,c失配时会 返回到前缀对应相等的c，但是该公共缀“abc”在之前两串匹配时已经显示匹配失败，所以现在会出现重复匹配的情况，此时应该为 nex[6]=nex[nex[6]];
规律（理解最重要）：
当 t j = t nex [ j ] , nex [ j ] = nex [ nex [ j ] ];
else nex [ j ] = nex [ j ];
1 while(j<len){ 2 if(k==-1||s[j]==s[k]){ 3 ++j,++k; 4 if(s[j]!=s[k])nex[j]=k; 5 else nex[j]=nex[k]; 6 //未失配情况，k、j代表的就是前缀与后缀相等部分的末尾，两者完全相同，所以直接再nex一次， 7 } 8 else k=nex[k]; 9 }
模板：
1 //建失配数组 2 void getnext(char *p,int nex[]){ 3 int len=strlen(p),k=-1,j=0; 4 nex[0]=-1; 5 while(j<len){ 6 if(k==-1||p[j]==p[k]){ 7 ++j,++k; 8 if(p[j]!=p[k])nex[j]=k; 9 else nex[j]=nex[k]; 10 } 11 else k=nex[k]; 12 } 13 } 14 //模式串匹配文本 15 int kmp(char *s,char *p){ 16 int i=0,j=0; 17 int len1=strlen(s),len2=strlen(p); 18 while(i<len1){ 19 if(j==-1||s[i]==p[j]) 20 i++,j++; 21 else 22 j=nex[j]; 23 if(j==len2) 24 j=-1,i--,mark++; 25 } 26 return mark; 27 }
原文：https://www.cnblogs.com/AndreaHtj/p/13500758.html
