●SPOJ 1811 Longest Common Substring

题链：

http://poj.org/problem?id=2774

题解：

求两个字符串（S,T）的最长公共子串。
对 S串建后缀自动机。
接下来就用这个自动机去求出能和 S串匹配的 T的每一个前缀的最长的后缀。
最终答案就是对每个 T的前缀得到的答案取最大值就好了。

代码：

#include<cstdio>

#include<cstring>

#include<iostream>

#define MAXN 250050

#define filein(x) freopen(#x".in","r",stdin);

#define fileout(x) freopen(#x".out","w",stdout);

using namespace std;

struct SAM{

	int size,last,q,p,nq,np;

	int pre[MAXN*2],step[MAXN*2],ch[MAXN*2][26];

	int Newnode(int a,int b){

		step[size]=a; memcpy(ch[size],ch[b],sizeof(ch[b]));

		return size++;

	}

	void Extend(int x){

		p=last; last=np=Newnode(step[p]+1,0);

		while(p&&!ch[p][x]) ch[p][x]=np,p=pre[p];

		if(!p) pre[np]=1;

		else{

			q=ch[p][x];

			if(step[q]!=step[p]+1){

				nq=Newnode(step[p]+1,q);

				pre[nq]=pre[q]; pre[q]=pre[np]=nq;

				while(p&&ch[p][x]==q) ch[p][x]=nq,p=pre[p];

			}

			else pre[np]=q;

		}

	}

	void Build(char *S){

		memset(ch[0],0,sizeof(ch[0]));

		size=1; last=Newnode(0,0); pre[last]=0;

		for(int i=0;S[i];i++) Extend(S[i]-'a');

	}

	int Match(char *T){

		p=1; int ans=0;

		for(int j=0,x,match=0;T[j];j++){ //与 T的每个前缀匹配

			x=T[j]-'a';

			if(ch[p][x]) match++,p=ch[p][x];

			else{

				while(p&&!ch[p][x]) p=pre[p];

				if(!p) match=0,p=1;

				else match=step[p]+1,p=ch[p][x];

			}

			ans=max(ans,match);

		}

		return ans;

	}

}suf;

char S[MAXN],T[MAXN];

int main()

{

	scanf(" %s %s",S,T);

	suf.Build(S);

	printf("%d",suf.Match(T));

	return 0;

}