spoj1811 Longest Common Substring，後綴自動機

spoj1811 Longest Common Substring，後綴自動機

spoj1811LCS

問兩個字符串最長公共子串。

做法很簡單。匹配成功，則tl++，失敗，從父指針回退，tl=t[now].len。

從這題可以清楚了解後綴自動機fa指針的性質：
指向一個狀態，這個狀態的接受串s[x..x+i]是與當前狀態的接受串後綴s[j-i..j]匹配是最長的一個。
這裡是不是發現了一個和KMP很像的性質？
KMP在失配時通過next數組回退，那麼這個回退到的位置i是s[0..i]與當前串的後綴s[j-i..j]匹配最長的一個。

所以。
利用後綴自動機可以求解一個串的子串（s[x..]）與另一個串的子串的最長匹配長度。

KMP可以求解一個串（s[0..]）與另一個串的子串的最長匹配長度。

#include
#include
#include
#include
using namespace std;
#define Maxn 250100

int root,last;//sam
int tots;

struct sam_node{
    int fa,son[26];
    int len;
    void init(int _len){len=_len;fa=-1;memset(son,-1,sizeof(son));}
}t[Maxn*2];//length*2

void sam_init(){
    tots=0;
    root=last=0;
    t[tots].init(0);
}

void extend(char ch){
    int w=ch-'a';
    int p=last;
    int np=++tots;t[tots].init(t[p].len+1);
    int q,nq;

    while(p!=-1&&t[p].son[w]==-1){t[p].son[w]=np;p=t[p].fa;}
    if (p==-1) t[np].fa=root;
    else{
        q=t[p].son[w];
        if (t[p].len+1==t[q].len){t[np].fa=q;}
        else{
            nq=++tots;t[nq].init(0);
            t[nq]=t[q];
            t[nq].len=t[p].len+1;
            t[q].fa=nq;t[np].fa=nq;
            while(p!=-1&&t[p].son[w]==q){t[p].son[w]=nq;p=t[p].fa;}
        }
    }
    last=np;
}

char s[Maxn];
char f[Maxn];

int work(int l2){
    int i,now=root,ind,tl=0;
    int ret=0;
    for(i=0;i