KMP和NEXT数组基本上是一起用的，有了NEXT数组，才有KMP算法，讲道理来说这两个都是基于最大前后缀和，也就是说需要用到KMP的时候必须先把NEXT数组先求出来，NEXT数组就是由所匹配的word的每个子串的前后缀和最大匹配得到的，说实话NEXT数组的算法给优化得已经很无解了，以至于至今我也只能理解一半。。
NEXT数组是由最大前后缀匹配和求得的，这个最大前后缀匹配和是什么东西呢，下面举个栗子。
比如说你要匹配的word叫abcabk
对于从0-i的子串（i是当前数组下标），
当i等于0时，子串为a，前缀和后缀都为空，所以最大匹配为0
当i等于1时，子串为ab，前缀和后缀分别为a和b，最大匹配为0
当i等于2时，子串为abc，前缀为a，ab，后缀为c，bc，最大匹配为0
当i等于3时，子串为abca，前缀为a，ab，abc后缀为a，ca，bca，最大匹配为1
当i等于4时，子串为abcab，前缀为a，ab，abc，abca，后缀为b，ab，cab，bcab，最大匹配为2
当i等于5时，子串为abcabk，前缀为a，ab，abc，abca，abcab，后缀为k，bk，abk，cabk，bcabk，最大匹配为0
所以NEXT数组就出来了，为：
0 0 0 1 2 0
但是这只是串比较小，对称度比较小的时候，如果要用程序实现又要怎么办呢。把所有子串都求出来？如果按照最暴力的写法，时间复杂度可能为O（n^3），虽然说word通常比较短，但是我们完全没有必要花辣么多时间在匹配NEXT数组上。
这种中间过程需要优化的，不用说，都想到了动态规划，压缩中间过程。
那我们再看看规律：
1、 当前面字符的前一个字符的对称程度为0的时候，只要将当前字符与子串第一个字符进行比较。这个很好理解啊，前面都是0，说明都不对称了，如果多加了一个字符，要对称的话最多是当前的和第一个对称。比如abcabk这个里面k的是0，那么后面的a的对称程度只需要看它是不是等于第一个字符a了。
#include <stdio.h>
#include <map>
#include <iostream>
#include <string.h>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <stdlib.h>
#define maxn 1000000+5
#define minn 100
using namespace std;
int *getNext(char *word){
int len = strlen(word);
int* next = (int*)malloc(maxn * sizeof(int));
memset(next,0,sizeof(next));
int j = 0,k = -1;
next[0] = -1;
while (j < len){
if (k == -1 || word[j] == word[k])
next[++j] = ++k;
else
k = next[k];
}
return next;
}
int kmp(char *text,char *word){
int l1 = strlen(text),l2 = strlen(word);
int i = 0,j = 0,sum = 0,*next = getNext(word);
while(i < l1){
if(j == -1 || text[i] == word[j]){
i++;
j++;
}
else
j = next[j];
if(j == l2) //匹配完全，计数器增加
sum++;
}
return sum;
}
int main(){
char str[maxn];
char ch[maxn];
int T;
scanf("%d",&T);
getchar();
while(T--){
scanf("%s %s",str,ch);
printf("%d\n",kmp(ch,str));
}
}
/*
5
HA
HAHAHA
WQN
WQN
ADA
ADADADA
BABABB
BABABABABABABABABB
DAD
ADDAADAADDAAADAAD
*/