自匹配理解:正常操作(不用kmp)O(len^2),kmp有点像dp,在匹配第n位时用前n-1位匹配好的表,
最后半写next半自匹配,完成了一个完整的自身与自身的kmp(它在匹配时只用到了已经算出来的部分next)
为什么只用了已经算出来的(解释):
代码pre_kmp中每次写next都是写在next[++i]里的,因为next的含义是在当前位置匹配失败时到转到的位置,
假设失败的位置是p,转到的位置是x,要满足的条件是1~x-1和(p-x+1)~(p-1)一样的,所以反过来,字符串一样了,
它是给后一维用的;
char a[maxn];int next[maxn];char b[maxn];//b自身的匹配表 void pre_kmp(char *a,int len,int *next) { int i=0,j; next[0]=j=-1; while(i