「SPOJ1812」Longest Common Substring II

2014年9月22日4,1020

A string is finite sequence of characters over a non-empty finite set Σ.

In this problem, Σ is the set of lowercase letters.

Substring, also called factor, is a consecutive sequence of characters occurrences at least once in a string.

Now your task is a bit harder, for some given strings, find the length of the longest common substring of them.

Here common substring means a substring of two or more strings.

Input

The input contains at most 10 lines, each line consists of no more than 100000 lowercase letters, representing a string.

Output

The length of the longest common substring. If such string doesn’t exist, print “0” instead.

Example

<strong>Input:</strong>
alsdfkjfjkdsal
fdjskalajfkdsla
aaaajfaaaa

<strong>Output:</strong>
2

<strong>Input:</strong>

alsdfkjfjkdsal

fdjskalajfkdsla

aaaajfaaaa

<strong>Output:</strong>

参见clj论文

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define N 200005
#define inf 1000000000
using namespace std;
int tot,cnt,n;
int s[N],l[N],cl[N],mn[N],fa[N],to[N][26];
int v[100005];
char ch[100005];
struct sam
{
	int p,q,np,nq;
	int last;
	sam(){
		cnt=++last;	
	}
	void extend(int c){
		p=last;last=np=++cnt;l[np]=l[p]+1;
		for(;p&&!to[p][c];p=fa[p])to[p][c]=np;
		if(!p)fa[np]=1;
		else 
		{
			q=to[p][c];
			if(l[p]+1==l[q])fa[np]=q;
			else 
			{
				nq=++cnt;l[nq]=l[p]+1;
				memcpy(to[nq],to[q],sizeof(to[q]));
				fa[nq]=fa[q];
				fa[q]=fa[np]=nq;
				for(;to[p][c]==q;p=fa[p])to[p][c]=nq;
			}
		}
	}
	void build(){
		scanf("%s",ch);
		n=strlen(ch);
		for(int i=0;i<n;i++)
			extend(ch[i]-'a');
	}
	bool pre()
	{
		if(scanf("%s",ch)==EOF)return 0;
		memset(cl,0,sizeof(cl));
	    n=strlen(ch);int tmp=0;
		for(int p=1,i=0;i<n;i++)
		{
			int c=ch[i]-'a';
			if(to[p][c])p=to[p][c],tmp++;
			else 
			{
				while(p&&!to[p][c])p=fa[p];
				if(!p)p=1,tmp=0;
				else tmp=l[p]+1,p=to[p][c];
			}
		    cl[p]=max(cl[p],tmp);
		}
		for(int i=cnt;i;i--)
		{
			int t=s[i];
			mn[t]=min(mn[t],cl[t]);
			if(cl[t]&&fa[t])cl[fa[t]]=l[fa[t]];
		}
		return 1;
	}
}sam;
int main()
{
    sam.build();
	for(int i=1;i<=cnt;i++)
		mn[i]=l[i];
	for(int i=1;i<=cnt;i++)
		v[l[i]]++;
	for(int i=1;i<=n;i++)v[i]+=v[i-1];
	for(int i=1;i<=cnt;i++)
		s[v[l[i]]--]=i;
	while(sam.pre());
	int ans=0;
	for(int i=1;i<=cnt;i++)
		ans=max(ans,mn[i]);	
	printf("%d\n",ans);
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#define N 200005

#define inf 1000000000

using namespace std;

int tot,cnt,n;

int s[N],l[N],cl[N],mn[N],fa[N],to[N][26];

int v[100005];

char ch[100005];

struct sam

{

int p,q,np,nq;

int last;

sam(){

cnt=++last;

}

void extend(int c){

p=last;last=np=++cnt;l[np]=l[p]+1;

for(;p&&!to[p][c];p=fa[p])to[p][c]=np;

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

else

{

q=to[p][c];

if(l[p]+1==l[q])fa[np]=q;

else

{

nq=++cnt;l[nq]=l[p]+1;

memcpy(to[nq],to[q],sizeof(to[q]));

fa[nq]=fa[q];

fa[q]=fa[np]=nq;

for(;to[p][c]==q;p=fa[p])to[p][c]=nq;

}

void build(){

scanf("%s",ch);

n=strlen(ch);

for(int i=0;i<n;i++)

extend(ch[i]-'a');

}

bool pre()

{

if(scanf("%s",ch)==EOF)return 0;

memset(cl,0,sizeof(cl));

n=strlen(ch);int tmp=0;

for(int p=1,i=0;i<n;i++)

{

int c=ch[i]-'a';

if(to[p][c])p=to[p][c],tmp++;

else

{

while(p&&!to[p][c])p=fa[p];

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

else tmp=l[p]+1,p=to[p][c];

}

cl[p]=max(cl[p],tmp);

}

for(int i=cnt;i;i--)

{

int t=s[i];

mn[t]=min(mn[t],cl[t]);

if(cl[t]&&fa[t])cl[fa[t]]=l[fa[t]];

}

return 1;

}

}sam;

int main()

{

sam.build();

for(int i=1;i<=cnt;i++)

mn[i]=l[i];

for(int i=1;i<=cnt;i++)

v[l[i]]++;

for(int i=1;i<=n;i++)v[i]+=v[i-1];

for(int i=1;i<=cnt;i++)

s[v[l[i]]--]=i;

while(sam.pre());

int ans=0;

for(int i=1;i<=cnt;i++)

ans=max(ans,mn[i]);

printf("%d\n",ans);

return 0;

}

« 「SPOJ8222」Substrings 「SPOJ7258」Lexicographical Substring Search »

hzwer.com _ Home | http://hzwer.com

「SPOJ1812」Longest Common Substring II

Input

Output

Example

分类目录

热门文章

Myfriends

近期评论