算法是字符串匹配领域的经典算法，相比暴力匹配的O(n∗m)时间复杂度，KMP

next

暴力匹配的问题在于：一旦字符不匹配，主串指针会回退到起始位置的下一位，模式串指针回退到

KMP

信息，当字符不匹配时，主串指针不回退，仅调整模式串指针到合适位置，避免重复比较。

举个简单例子：模式串abaabc匹配到某位置失败时，不需要从头匹配，而是根据已匹配部分的公共前后缀，直接跳到最优位置继续匹配。

前缀：字符串中不包含最后一个字符的所有以第一个字符开头的子串（如aba的前缀：a、ab）

后缀：字符串中不包含第一个字符的所有以最后一个字符结尾的子串（如aba的后缀：a、ba）

最长相等公共前后缀：前缀和后缀中长度最长且内容相等的子串长度（如aba的最长相等公共前后缀长度为

1，对应子串a）

#include<iostream>
using
next[t.length()];getNext(t,next);cout
<<
"\"的next数组：";show(next,t.length());int
pos
-1)printf("未从<%s>中找到<%s>\n",s,t);elseprintf("匹配成功！
\n%s\n%*s%s\n",s.c_str(),pos,"",t.c_str());return
}int
i=1;i<length;i++)//判断从长度1到length-1的前缀与后缀是否相等if(str.substr(0,i)==str.substr(length-i,i))pub
i;return
t.length();while(i<sL&&j<tL){if(j==-1||s[i]==t[j]){i++;j++;}elsej=next[j];}if(j==tL)return
i-tL;elsereturn
i=0;i<n;i++)printf("<%d>
",arr[i]);puts("");
id="1getpub-函数求最长公共前后缀">(1)getPub
函数（求最长公共前后缀）

实现逻辑：遍历

next[1]

next

匹配失败：j

next[j]（模式串指针回退到最优位置），i不回退；

模式串"abaabc"的next数组：<-1>
<0>
class="post-meta-container">