关于KMP
用途:字符串匹配,求周期
性质:(i-next[i])是循环节(画图可知)
fail[0]=fail[1]=1;
for(int i=1;i<n;++i){
while(j&&s[i]!=s[j])j=fail[j];
if(s[i]==s[j])j++;
fail[i+1]=j;
}//对模式串求next
fail[0]=fail[1]=1;
for(int i=1;i<n;++i){
while(j&&s[i]!=s[j])j=fail[j];
if(s[i]==s[j])j++;
fail[i+1]=j;
}//对模式串求next