恩，学完后缀数组，干脆想把AC自动机也给学了，然后发现貌似需要KMP的基础，于是打算顺便复习一下，顺便写个博客，增加下浏览量。
KMP算法是什么，顾名思义(看毛片，大家都会吧，，，感觉黄段子乖乖的，好羞涩，)是K，M，P三个人几乎同时发现的一种线性字符串匹配算法。说白了就是一个比较短的a串和一个比较长的b串，让你看a串能否匹配于b串的某一个位置。
传统的方法，就是n^2暴力匹配，虽然在随机数据下，这个算法其实非常高效，然而考试并不会让你愉快的n^2水过，所以我们需要学习KMP 算法。
先给出一个模板
struct kmp { char a[20000],b[2000000]; int nxt[20000]; int lena,lenb; void scanfa() { scanf("%s",a); } void scanfb() { scanf("%s",b); } void nxt_init() { int p = 0; for (int i = 1;i < lena;i++) { while (p && a[p] != a[i]) p = nxt[p - 1]; if (a[p] == a[i]) p++; nxt[i] = p; } } kmp() { memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(nxt,0,sizeof(nxt)); } void init() { memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(nxt,0,sizeof(nxt)); } int match() { lena = strlen(a); lenb = strlen(b); nxt_init(); int p = 0; for (int i = 0;i < lenb;i++) { while (p && a[p] != b[i]) p = nxt[p - 1]; if (a[p] == b[i]) p++; if (p == lena) return i - lena + 2; } return -1; } }; 然后我们来一步一步考虑，我们在传统的n^2算法中浪费了什么，我们每次，可能短串长lena，我们匹配到lena-1位失败了，这样子，我们下一次还要从头开始匹配a串，显然之前匹配的lena-1位都浪费了，所以kmp算法的核心就是前面我已经匹配过了，那我就不再进行匹配。进行kmp算法，我们首先需要求出核心，nxt数组
给出一个nxt数组的例子
a b r a c a d a b r a 0 0 0 1 0 1 0 1 2 3 4
为了描述方便，我们作出定义，较短串为a串，较长串为b串。
如果我们在用a串匹配b串在第0位失败了的话，显然从b下一位从a的第0位开始匹配。
同理再举几个例子，比如我们如果在b串匹配a时最后一个a匹配失败，那么我们可以在b的下以为从a的第4位开始匹配，为什么呢，我们观察一下，0-4位和7-9位是相同的，显然我们从上一位匹配，匹配到了最后一位a才失败，那我们从b的下一位开始匹配，显然，我们可以从下标为4的地方开始往下匹配，下标0-3，显然一定匹配，因为你b匹配失败的那一位的前面三位，等于a中后面的abr，才会匹配到最后以为，那么显然我们从匹配失败的位置，从a字符串考前的abr开始匹配是没有问题的，并且已经成功的匹配了0-2位。好那么我们考虑如何求出这个nxt数组，我们想如果我们球nxt[i]，显然我们需要先看nxt[i-1]，如果nxt[i-1]所指向的那个下标等于a[i]，那么显然nxt[i] = nxt[i - 1] + 1，否则就继续往前找nxt。
求出nxt之后，我们就可以非常愉快的进行匹配了，从b串的0位开始，每次如果不等，就顺着nxt跳a串直到0，如果相等就比较下一位，如果最后a串比到头，就证明找到了，返回即可，详细的，可以参考上面的代码。
