【SPOJ1811】Longest Common Substring

  构造出SAM以后就可以直接做了，和KMP很像。

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

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

	SAM() {last=cnt=1;}

	void Extend(int c)
	{
		int x=++cnt,p;
		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[p].len==st[q].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[q].link=st[x].link=v;
			}
		}
		last=x;
	}

	int LCS(char *ch,int n)
	{
		int res=0;
		for (int i=0,p=1,len=0;i<n;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++;
			res=max(res,len);
		}
		return res;
	}
}M;

char ch[maxn];
int n;

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