后缀自动机(SAM):SPOJ Longest Common Substring II

时间:2021-03-17 17:13:45

Longest Common Substring II

Time Limit: 2000ms
Memory Limit: 262144KB

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

Input:
alsdfkjfjkdsal
fdjskalajfkdsla
aaaajfaaaa Output:
2   这题是找一些字符串的最长公共子串。
  这里对其中一个建SAM,然后跑其他字符串,在每一个字符串中,记录SAM节点中每个节点对应的最长长度,最后在所有字符串中SAM的最长长度取MIN,答案最后再在对每个位置的最小值取MAX。
 #include <iostream>
#include <cstdio>
#include <cstring>
using namespace std; struct SAM{
int ch[][],len[],fa[],last,cnt;
void Init()
{
memset(fa,,sizeof(fa));
last=cnt=;
}
void Insert(int c)
{
int p=last,np=last=++cnt;
len[np]=len[p]+;
while(p&&!ch[p][c])
ch[p][c]=np,p=fa[p];
if(!p)
fa[np]=;
else{
int q=ch[p][c];
if(len[p]+==len[q])
fa[np]=q;
else{
int nq=++cnt;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
len[nq]=len[p]+;
fa[nq]=fa[q];
fa[q]=fa[np]=nq;
while(p&&ch[p][c]==q)
ch[p][c]=nq,p=fa[p];
}
}
}
}sam;
char s[];
int ans[],f[];
int main()
{
memset(ans,,sizeof(ans));
sam.Init();
scanf("%s",&s);
for(int i=;s[i];i++)
sam.Insert(s[i]-'a');
while(~scanf("%s",s))
{
memset(f,,sizeof(f));
int node=,len=;
for(int i=;s[i];i++)
{
int c=s[i]-'a';
while(node&&!sam.ch[node][c])
node=sam.fa[node];
if(!node)
node=,len=;
else
len=sam.len[node]+,node=sam.ch[node][c];
if(len>f[node])f[node]=len;
}
for(int i=;i<=sam.cnt;i++)
ans[i]=min(ans[i],f[i]);
}
int ret=;
for(int i=;i<=sam.cnt;i++)
ret=max(ret,ans[i]);
printf("%d\n",ret);
return ;
}