【接尾辞自動機(入門)について】[SPOJLCS 2]Longest Common Substring II

テーマの大意
n個の文字列n<=10が与えられ、各文字列の長さは100000未満であり、それらの最長共通列の長さを求める.
ぶんせき
接尾辞オートマトンについて
復習の過程で接尾辞の自動機を見て、多くの初学の時に分からなかった問題を解決しました.まず、接尾辞オートマトンの各ノードが表す終点等価クラスを明確にし、ルートノードからリーフノードまで歩くと接尾辞に対応し、lenはこの終点等価クラスの中で最も長い文字列の長さを表し、この中終点等価クラスの文字列の長さは連続し、短い文字列は長い接尾辞である.接尾辞エッジが指すノードに対応する文字列は、このノードに対応する文字列の接尾辞である.接尾辞エッジが指すノードに対応する終点等価クラスの終点は、現在のノードの終点等価クラスに対応する終点を含む.
u→fail=v⇒endpos(u)⊊endpos(v)len(v)max+1=len(u)min
構築中
pは
Lastは接尾辞に沿って最初の文字を歩きます
c移行ノード、
qは
p経文字
c移転してきた.我々は
qに対応する終点等価類の増加
cこの位置.

q−>len≠p−>len+1は、pからqに移行することはq点に対応する最も長い文字列ではないが、これはこの終点を増加させることができる最も長い文字列であり、qに対応するその長さより長い文字列はこの終点を増加させることができないことを示しているので、ノードnqを新規作成し、qの情報を彼(len,fail,ch)、nq→len=p→len+1にコピーし、q→fial=nq,np→fial=nqであり、接尾辞のエッジに沿って歩き、すべての文字cが転送され、qに転送された転送をnqにリダイレクトする.なぜchもコピーするのですか?このノードに対応する文字列に遷移したエッジに対応する文字が形成された文字列の終点はこのノードの終点とは関係ないので,このノードの息子ノードに対応する文字列が変わらないことを保証する.

q−>len=p−>len+1であるとnp→fial=q

となる.
この問題
各ノードは、現在の文字列がこのノードに対応する文字列の最大長nmxに一致し、すべての文字列がこのノードに対応する文字列の最大長の最小値mxに一致する2つの値を保存します.次に、マッチングが完了するたびに接尾辞のエッジに沿ってnmxを更新します.そうしないと、nmxでmxを更新するときにエラーが発生します.
ans=max(p→mx)
コード#コード#

#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF 0x7fffffff
#define MAXN 100000
using namespace std;
void Read(int &x){
    char c;
    while(c=getchar(),c!=EOF)
        if(c>='0'&&c<='9'){
            x=c-'0';
            while(c=getchar(),c>='0'&&c<='9')
                x=x*10+c-'0';
            ungetc(c,stdin);
            return;
        }
}
struct node{
    int len,mx,nmx;
    node *ch[26],*fail;
}tree[MAXN*2+10],*tcnt=tree,*root=tcnt,*l=tcnt,*r[MAXN*2+10];
char s[MAXN+10];
int ans,b[MAXN+10];
void insert(char c){
    c-='a';
    node *p=l,*np=++tcnt,*q,*nq;
    l=np;
    np->len=p->len+1;
    while(p&&!p->ch[c])
        p->ch[c]=np,p=p->fail;
    if(!p)
        np->fail=root;
    else{
        q=p->ch[c];
        if(q->len==p->len+1)
            np->fail=q;
        else{
            nq=++tcnt;
            *nq=*q;
            nq->len=p->len+1;
            q->fail=nq;
            np->fail=nq;
            while(p&&p->ch[c]==q)
                p->ch[c]=nq,p=p->fail;
        }
    }
}
void read(){
    scanf("%s",s);
    for(int i=0;s[i];i++)
        insert(s[i]);
}
void solve(){
    int i,len,tot;
    node *p;
    for(p=tree;p<=tcnt;p++){
        p->mx=p->len,p->nmx=0;
        b[p->len]++;
    }
    for(i=1;s[i-1];i++)
        b[i]+=b[i-1];
    for(p=tree;p<=tcnt;p++)
        r[--b[p->len]]=p;
    tot=tcnt-tree;
    while(~scanf("%s",s)){
        p=root;
        len=0;
        for(i=0;s[i];i++){
            s[i]-='a';
            if(p->ch[s[i]]){
                p=p->ch[s[i]];
                p->nmx=max(p->nmx,++len);
            }
            else{
                while(p&&!p->ch[s[i]])
                    p=p->fail;
                if(!p)
                    p=root,len=0;
                else{
                    len=p->len+1;
                    p=p->ch[s[i]];
                    p->nmx=max(p->nmx,len);
                }
            }
        }
        for(i=tot;i;i--){
            r[i]->fail->nmx=max(r[i]->nmx,r[i]->fail->nmx);//   r[i]->len    ，        r[i]->mx
            r[i]->mx=min(r[i]->mx,r[i]->nmx);
            r[i]->nmx=0;
        }
    }
    for(p=tree;p<=tcnt;p++)
        ans=max(ans,p->mx);
}
int main()
{
    read();
    solve();
    printf("%d
",ans);
}