http://codevs.cn/problem/3160/
sam的裸题。。。（之前写了spoj上另一题sam的题目，但是spoj被卡评测现在还没评测完QAQ打算写那题题解时再来详细介绍sam的。。。。那就再等等吧。
求两个串的lcs话，就是先建立a串的sam，然后用b的字串去匹配a中。
因为sam中的转移可以直接对应所有后缀的开头，因此匹配的时候是可以直接找到这个后缀开头，然后继续转移，直至找到整个串。而因为sam中的parent指针就如ac自动机中的fail指针差不多，唯一的区别是sam的parent指针转移到的节点是自己的后缀（就是S到当前节点就是一个原串的前缀，而上面说的就是这个前缀的后缀，而且长度每次都递减，因此能找到最大匹配）
所以不断找然后更新即可。
如果还不懂详看clj论文
#include cstdio #include cstring #include cmath #include string #include iostream #include algorithm #include queue #include set #include map using namespace std;typedef long long ll;#define rep(i, n) for(int i=0; i ++i)#define for1(i,a,n) for(int i=(a);i =(n);++i)#define for2(i,a,n) for(int i=(a);i ++i)#define for3(i,a,n) for(int i=(a);i =(n);--i)#define for4(i,a,n) for(int i=(a);i --i)#define CC(i,a) memset(i,a,sizeof(i))#define read(a) a=getint()#define print(a) printf("%d", a)#define dbg(x) cout (#x) " = " (x) endl#define error(x) (!(x)?puts("error"):0)#define rdm(x, i) for(int i=ihead[x]; i; i=e[i].next)inline const int getint() { int r=0, k=1; char c=getchar(); for(; c '0'||c c=getchar()) if(c=='-') k=-1; for(; c ='0' c ='9'; c=getchar()) r=r*10+c-'0'; return k*r; }struct sam { static const int N=200005; int c[N][26], l[N], f[N], root, last, cnt; sam() { cnt=0; root=last=++cnt; } void add(int x) { int now=last, a=++cnt; last=a; l[a]=l[now]+1; for(; now !c[now][x]; now=f[now]) c[now][x]=a; if(!now) { f[a]=root; return; } int q=c[now][x]; if(l[q]==l[now]+1) { f[a]=q; return; } int b=++cnt; memcpy(c[b], c[q], sizeof c[q]); l[b]=l[now]+1; f[b]=f[q]; f[q]=f[a]=b; for(; now c[now][x]==q; now=f[now]) c[now][x]=b; void build(char *s) { int len=strlen(s); rep(i, len) add(s[i]-'a'); int find(char *s) { int ret=0, len=strlen(s), now=1, t=0; rep(i, len) { int x=s[i]-'a'; if(c[now][x]) now=c[now][x], ++t; else { while(now !c[now][x]) now=f[now]; if(!now) now=root, t=0; else t=l[now]+1, now=c[now][x]; ret=max(ret, t); return ret;const int N=100005;char s[N];int main() { scanf("%s", s); a.build(s); scanf("%s", s); printf("%d", a.find(s)); return 0;
yeshowmuchiloveyoumydearmotherreallyicannotbelieveit
yeaphowmuchiloveyoumydearmother