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