KMP：HDU4763 Theme Section 深刻理解next数组

KMP模板套了那么久，没真正理解next可不行！

string s;
next[i]:字符s[i] 与 (aaxoaaaaa)真前缀 失配时指向串的位置（跳转数组）
某种意义上：next[i]等于P[0]...P[i - 1]最长的相同真前后缀的长度
例如： a a x o a a a a a
next:-1 0 1 0 0 1 2 2 2
              * * *
*1:若这里的a失配之后指向s[0]:a
*2:若这里的a失配之后指向s[1]:a
*3:若这里的a失配之后指向s[2]:x

看了这么久，发现其实KMP就是固定起点（前缀）的字符串匹配，一定是要看前缀的。

==============分割线============

题意：给你一个母串：（子串）*（子串）*（子串），就是求一个最长的母串前缀(zilen)，既出现在母串中间[zilen,mulen-zilen],又是母串的结尾

可以利用next跳转，
1.从最后面开始，j=len
2.那么处理的子串长度就是next[j](next数组一直到字符串结尾的后一位，因为这里才有产生失配）
3.一直递归等于j=next[j],直到j==-1结束

代码如下：

#include<iostream>
#include<algorithm>
#include<string.h>
#include<cstring>
#include<string>
#include<cstdio>
using namespace std;
const int maxn=1e6+100;
const int maxm=26000;
int nex[maxn];//next数组
//对母串生成next
void getnext(string s){
memset(nex,0,sizeof(nex));
int i=0;
int j=-1;
    nex[0]=-1;
int len=s.size();
while(i<len){
if(j==-1||s[i]==s[j])nex[++i]=++j;
else j=nex[j];
    }
} 
//输入当前字符串，当前位置（前缀子串的长度），母串长度
bool subkmp(string s,int pos,int mulen){
int j=0;
for(int i=pos;i<mulen-pos;i++){
while(j>0&&s[i]!=s[j])j=nex[j];
if(s[j]==s[i])j++;
if(j==pos)return true;
    }
return false;
}
int main(){
int t;
string s;
cin>>t;
while(t--){
cin>>s;
int len=s.size();
if(len<3)printf("0\n");
else{
            getnext(s); 
//for(int i=0;i<=len;i++)printf("%c nex[%d]=%d\n",s[i],i,nex[i]);//可以输出查看next,慢慢理解
int maxlen=0;
int j=len;
while(nex[j]>=0){//nex[j]指到后缀与前缀刚失配的位置，一直到-1 
if(subkmp(s,nex[j],len)){
                    maxlen=max(maxlen,nex[j]);
                }
                j=nex[j];
            }
if(maxlen)printf("%d\n",maxlen);
else printf("0\n");
        }

    }
return 0;
}

同类型题目：HDU2594

这里是KMP专题，大家可以自己VJ克隆了去写，有一些其实是后缀数组的，可以先不写
希望和大家一起共同进步！~再见~