地址:http://www.spoj.com/problems/LCS/
题面:
LCS - Longest Common Substring
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 simple, for two 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 exactly two lines, each line consists of no more than 250000 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 Output:
3 思路:
对于串a建立后缀自动机, 然后让串b在sam上能走,记录到达每个状态时的长度,取个max就行。
#include <bits/stdc++.h> using namespace std; struct SAM
{
static const int MAXN = 3e5 * ;//大小为字符串长度两倍
static const int LetterSize = ;
int tot, last, ch[MAXN][LetterSize], fa[MAXN], len[MAXN]; void init( void)
{
last = tot = ;
len[] = ;
memset(ch,,sizeof ch);
memset(fa,,sizeof fa);
} void add( int x)
{
int p = last, np = last = ++tot;
len[np] = len[p] + ;
while( p && !ch[p][x]) ch[p][x] = np, p = fa[p];
if( p == )
fa[np] = ;
else
{
int q = ch[p][x];
if( len[q] == len[p] + )
fa[np] = q;
else
{
int nq = ++tot;
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][x] == q)
ch[p][x] = nq, p = fa[p];
}
}
}
};
char sa[],sb[];
SAM sam;
int main(void)
{
scanf("%s%s",sa,sb);
int len=strlen(sa),ans=;
sam.init();
for(int i=;i<len;i++)
sam.add(sa[i]-'a');
len=strlen(sb);
for(int i=,p=,cnt=;i<len;i++)
{
int k=sb[i]-'a';
if(sam.ch[p][k])
p=sam.ch[p][k],cnt++;
else
{
while(p&&!sam.ch[p][k]) p=sam.fa[p];
if(p==)
p=,cnt=;
else
cnt=sam.len[p]+,p=sam.ch[p][k];
}
ans=max(ans,cnt);
}
printf("%d\n",ans);
return ;
}