【SPOJ1811】Longest Common Substring

Zarxdy34 posted @ 2016年4月02日 10:21 in SPOJ with tags SAM , 202 阅读

  构造出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;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Copyright © 2007

Webdesign, tvorba www stránek

Valid XHTML 1.1