参考博客：http://blog.csdn.net/dyx404514/article/details/41831947
附模板：
#include<cstring> #include<cstdio> using namespace std; const int MAXN = 100010; int next[MAXN], ex[MAXN]; void getNext(char *str) { int i = 0, j, po, len = strlen(str); next[0] = len;//初始化next[0] while (str[i] == str[i + 1] && i + 1 < len)//计算next[1] i++; next[1] = i; po = 1;//初始化po的位置 for (i = 2;i < len;i++) { if (next[i - po] + i < next[po] + po)//第一种情况，可以直接得到next[i]的值 next[i] = next[i - po]; else//第二种情况，要继续匹配才能得到next[i]的值 { j = next[po] + po - i; if (j < 0) j = 0;//如果i>po+next[po],则要从头开始匹配 while (i + j < len&&str[j] == str[j + i])//计算next[i] j++; next[i] = j; po = i;//更新po的位置 } } } void exKmp(char *s1, char *s2) { int i = 0, j, po, len = strlen(s1), l2 = strlen(s2); getNext(s2);//计算子串的next数组 while (s1[i] == s2[i] && i < l2&&i < len)//计算ex[0] i++; ex[0] = i; po = 0;//初始化po的位置 for (i = 1;i < len;i++) { if (next[i - po] + i < ex[po] + po)//第一种情况，直接可以得到ex[i]的值 ex[i] = next[i - po]; else//第二种情况，要继续匹配才能得到ex[i]的值 { j = ex[po] + po - i; if (j < 0) j = 0;//如果i>ex[po]+po则要从头开始匹配 while (i + j < len&&j < l2&&s1[j + i] == s2[j])//计算ex[i] j++; ex[i] = j; po = i;//更新po的位置 } } } int main() { return 0; }