|
SPOJ Problem Set (classical)
1812. Longest Common Substring II
Problem code: LCS2
|
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
Notice: new testcases added
第一个串建SAM,剩下的串在上面跑....记录下每个节点的最小匹配长度(初始值是 len 即能表示的最长后缀),
从后向前更新fa节点的LCS....
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=110000;
struct SAM_Node
{
SAM_Node *fa,*next[26];
int len,id,pos;
SAM_Node(){}
SAM_Node(int _len)
{
fa=0; len=_len;
memset(next,0,sizeof(next));
}
};
SAM_Node SAM_node[maxn*2],*SAM_root,*SAM_last;
int SAM_size;
SAM_Node *newSAM_Node(int len)
{
SAM_node[SAM_size]=SAM_Node(len);
SAM_node[SAM_size].id=SAM_size;
return &SAM_node[SAM_size++];
}
SAM_Node *newSAM_Node(SAM_Node *p)
{
SAM_node[SAM_size]=*p;
SAM_node[SAM_size].id=SAM_size;
return &SAM_node[SAM_size++];
}
void SAM_init()
{
SAM_size=0;
SAM_root=SAM_last=newSAM_Node(0);
SAM_node[0].pos=0;
}
void SAM_add(int x,int len)
{
SAM_Node *p=SAM_last,*np=newSAM_Node(p->len+1);
np->pos=len; SAM_last=np;
for(;p&&!p->next[x];p=p->fa)
p->next[x]=np;
if(!p)
{
np->fa=SAM_root;
return ;
}
SAM_Node *q=p->next[x];
if(q->len==p->len+1)
{
np->fa=q;
return ;
}
SAM_Node *nq=newSAM_Node(q);
nq->len=p->len+1;
q->fa=nq; np->fa=nq;
for(;p&&p->next[x]==q;p=p->fa)
p->next[x]=nq;
}
char str[maxn],other[maxn];
int LCS[maxn*2],len,n;
int c[maxn*2]; SAM_Node *top[maxn*2];
int main()
{
scanf("%s",str);
len=strlen(str);
SAM_init();
for(int i=0;i<len;i++)
SAM_add(str[i]-'a',i+1);
for(int i=0;i<SAM_size;i++)
c[SAM_node[i].len]++;
for(int i=1;i<=len;i++)
c[i]+=c[i-1];
for(int i=0;i<SAM_size;i++)
top[--c[SAM_node[i].len]]=&SAM_node[i];
while(scanf("%s",other)!=EOF)
{
n++;
int len2=strlen(other);
SAM_Node* now=SAM_root;
int temp=0;
for(int i=0;i<len2;i++)
{
int x=other[i]-'a';
if(now->next[x])
{
temp++;
now=now->next[x];
}
else
{
while(now&&now->next[x]==0)
now=now->fa;
if(now)
{
temp=now->len+1;
now=now->next[x];
}
else
{
temp=0;
now=SAM_root;
}
}
if(temp>LCS[now->id])
LCS[now->id]=temp;
}
for(int i=SAM_size-1;i>=0;i--)
{
if(LCS[top[i]->id]<top[i]->len)
top[i]->len=LCS[top[i]->id];
if(top[i]->fa&&LCS[top[i]->fa->id]<LCS[top[i]->id])
LCS[top[i]->fa->id]=LCS[top[i]->id];
LCS[top[i]->id]=0;
}
}
int ans=0;
for(int i=1;i<SAM_size;i++)
{
if(ans<SAM_node[i].len)
ans=SAM_node[i].len;
}
printf("%d\n",ans);
return 0;
}
| 
转播
