【SPOJ1812】Longest Common Substring II

  给第一个串建SAM，然后之后的每一个串都和第一个串匹配，对于每个状态记录当前串在当前状态下的LCS，最后把答案合并一下就好了。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=100010;

struct SAM
{
	struct State
	{
		int next[26];
		int link;
		int len;
	}st[maxn<<1];

	int last,cnt,n;
	int ccnt[maxn];
	int T[maxn<<1];
	int temp[maxn<<1],minl[maxn<<1];
	
	SAM() {last=cnt=1;}

	void Extend(int c)
	{
		int x=++cnt,p;n++;
		st[x].len=st[last].len+1;
		for (p=last;p && !st[p].next[c];p=st[p].link) st[p].next[c]=x;
		if (!p) st[x].link=1;
		else {
			int q=st[p].next[c];
			if (st[q].len==st[p].len+1) st[x].link=q;
			else {
				int v=++cnt;
				st[v]=st[q];
				st[v].len=st[p].len+1;
				for (;p && st[p].next[c]==q;p=st[p].link) st[p].next[c]=v;
				st[x].link=st[q].link=v;
			}
		}
		last=x;
	}

	void Topo()
	{
		for (int i=1;i<=cnt;i++) ccnt[st[i].len]++;
		for (int i=1;i<=n;i++) ccnt[i]+=ccnt[i-1];
		for (int i=1;i<=cnt;i++) T[ccnt[st[i].len]--]=i;
		for (int i=1;i<=cnt;i++) minl[i]=st[i].len;
	}

	int LCS(char *ch,int cn)
	{
		int res=0;
		memset(temp,0,sizeof(temp));
		for (int i=0,p=1,len=0;i<cn;i++)
		{
			int c=ch[i]-'a';
			while (p && !st[p].next[c]) p=st[p].link,len=st[p].len;
			if (!p) p=1,len=0;else p=st[p].next[c],len++;
			temp[p]=max(temp[p],len);
		}
		for (int i=cnt;i;i--)
		{
			int v=T[i];
			minl[v]=min(minl[v],temp[v]);
			res=max(res,minl[v]);
			if (temp[v]) temp[st[v].link]=max(temp[st[v].link],temp[v]);
		}
		return res;
	}
}M;

char ch[maxn];
int n,ans;

int main()
{
	scanf("%s",ch);
	n=strlen(ch);
	for (int i=0;i<n;i++) M.Extend(ch[i]-'a');
	M.Topo();
	ans=n;
	while (scanf("%s",ch)!=EOF) ans=M.LCS(ch,strlen(ch));
	printf("%d\n",ans);
	return 0;
}