SPOJ1811/LCS/Longest Common Substring

Posted on By 二价氢

后缀自动机Suffix Automaton/SAM

将字符串A建立后缀自动机,用字符B在自动机上跑一遍,跑得最远的位置就是答案~

备注:此题卡\(O(n \log n)\)卡到丧心病狂!

AC-Code

/*
 * SPOJ 1811 LCS
 * Longest Common Substring
 * 后缀树/后缀自动机
 */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=250005;
char a[maxn],b[maxn];
int la,lb;
struct t{
	int l;
	t *f,*n[26];
	t (int _l=0,t *_f=NULL):l(_l),f(_f){
		memset(n,0,sizeof(n));
	};
};
t *build(char *s,int ls)
{
	t *root=new t(0,NULL),*cur=root;
	for (int i=0;i<ls;i++)
	{
		int x=s[i]-'a';
		t *p=cur;
		cur=new t(i+1,NULL);
		for (;p && p->n[x]==NULL;p=p->f)
			p->n[x]=cur;
		if (!p)
			cur->f=root;
		else
		{
			t *q=p->n[x];
			if (q->l == p->l+1)
				cur->f=q;
			else
			{
				t *r=new t();*r=*q;
				r->l=p->l+1;
				q->f=r;
				cur->f=r;
				for (;p && p->n[x]==q;p=p->f)
					p->n[x]=r;
			}
		}
	}
	return root;
}
int main()
{
	scanf("%s%s",a,b);
	la=strlen(a),lb=strlen(b);
	t *p=build(a,la),*root=p;
	int ret=0;
	for (int i=0,l=0;i<lb;i++)
	{
		int x=b[i]-'a';
		if (p->n[x])
			l++,p=p->n[x];
		else
		{
			while (p && p->n[x]==NULL)
				p=p->f;
			if (p)
			{
				l=p->l+1;
				p=p->n[x];
			}else
			{
				p=root;
				l=0;
			}
		}
		if (ret<l)
			ret=l;
	}
	printf("%d\n",ret);
	return 0;
}