参考博客： http://www.61mon.com/index.php/archives/183/ http://blog.csdn.net/yutianzuijin/article/details/11954939/
kmp算法： 通过已匹配成功的串来获得信息，决定子串需要移动的位置，注意这里的移动不是真的移动，而是直接更换下标位置。在上面的例子中可以看到，当在d发生匹配失败时，通过next[ 下标[d] ](为什么不是next[ 下标[c] ]，因为next的下标是从1开始)的值，使子串移动，然后继续比较
next数组： next数组的求解与kmp相同，只是主串和子串都是自身，两者进行匹配，记录出最大前缀的坐标位置，因为需要记录匹配成功的个数，而个数就是最大前缀的坐标位置
代码解析： 这里只介绍为什么是j=next[j]，首先很明确，j=next[j]是来实现子串移动的，当最后的位置失配时，而前面的公共位置是匹配成功的，移动子串进行比较，而移动之后的公共位置也是匹配成功的，如果最后位置又失配，那么继续移动，使j=next[j]，直到最后位置匹配成功或无法移动为止
附模板：
#include<cstdio> #include<cstring> using namespace std; const int MAXN = 1000 + 5; char pristr[] = { "ajdzjfaoiuq.,zoiaamerjoiadfkem.,mzlfdka;dskafqoiwecmafdafabvabacaflkcqwancz;ascajlfajfazn;dasdafdssdafdafzaenrzowrnPfdeasfjdaf'goisjadlkjfigoZjfaepasafdfaeoasdfsdasdafiueqrjzcoiuoannreqiuznqeyuznfanfuahiaqorezaadsqrpewqroqriafdeqrqmefzdxlkfdgpfs,z;flpewoKmfak;lfkeqqeropizmcvapifta,/fdap<asdfgearearardasdafdsfeqrqamdsf;lkzclkafdewqpoirfka3kfldakrpoeqirpokzlxkvlkmdagkiadfafaf;erafdsareeaqreaeossssreqqldaprqdasdafrewafaferaasdfadfererafderaerzfderq" }; char substr[] = { "dasdafd" }; int nxt[MAXN]; void getNext(char *arr,int *next) { nxt[0] = -1; int j = 0, i = 1; while (i<strlen(arr)) { if (j == -1 || arr[j] == arr[i]) nxt[i++] = ++j; else j = nxt[j]; } } int toKmp(char *pristr,char *substr,int* next) { getNext(substr, next); int j = 0, i = 0; while (i<strlen(pristr)) { if (j == -1 || substr[j] == pristr[i]) i++,j++; else j = nxt[j]; if (j == strlen(substr)) { printf("%d\n", i - j); j = nxt[j]; } } if (j == strlen(substr)) return i - j; return -1; } //int toTest(char *pristr, char *substr) //{ // for (int i = 0;i < strlen(pristr);i++) // { // int tmp = 0; // for (int j = 0;j < strlen(substr);j++) // { // if (pristr[i + j] == substr[j]) // tmp++; // else break; // } // if (tmp == strlen(substr)) // printf("%d\n", i); // } // return -1; //} int main() { toKmp(pristr, substr, nxt); //puts(""); //toTest(pristr, substr); return 0; }