公共串

Time Limit: 3 Sec Memory Limit: 128 MB

Description

给出几个由小写字母构成的单词,求它们最长的公共子串的长度。
  任务:
  l  读入单词
  l  计算最长公共子串的长度
  l  输出结果

Input

文件的第一行是整数 n ,表示单词的数量。接下来n行每行一个单词,只由小写字母组成,单词的长度至少为1,最大为2000。

Output

仅一行,一个整数,最长公共子串的长度。

Sample Input

3
 abcb
 bca

acbc

Sample Output

HINT

2 <= n <= 5

Solution

因为要求所有串的最长公共子串,所以我们运用SAM,先对第一个串(基本串)构建一个SAM,然后用后面的串匹配即可。

记录 L[i] 表示当前串和基本串在 i 这个状态匹配的最长长度。显然,一个状态对答案的贡献是所有串和基本串匹配时 L[i] 的最小值

然后取一个最大值即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<bits/stdc++.h>
using namespace std;

const int ONE=4005;
const int INF=2147483640;

int T,n;
char str[ONE];
int ans[ONE], q[ONE], L[ONE];
int len[ONE], a[ONE][27], fa[ONE], v[ONE];
int last, cnt;
int Ans;

int get()
{
int res=1,Q=1;char c;
while( (c=getchar())<48 || c>57 )
if(c=='-')Q=-1;
res=c-48;
while( (c=getchar())>=48 && c<=57 )
res=res*10+c-48;
return res*Q;
}

struct SAM
{
SAM() {last = cnt = 1;}
void Add(int c)
{
int x = last, New = last = ++cnt;
len[New] = len[x] + 1;
while(x && !a[x][c]) a[x][c] = New, x = fa[x];
if(!x) {fa[New] = 1; return;}

int q = a[x][c];
if(len[x] + 1 == len[q]) fa[New] = q;
else
{
int Nq = ++cnt; len[Nq] = len[x] + 1;
memcpy(a[Nq], a[q], sizeof(a[q]));
fa[Nq] = fa[q];
fa[New] = fa[q] = Nq;
while(a[x][c] == q) a[x][c] = Nq, x = fa[x];
}
}

void Pre()
{
for(int i=1; i<=cnt; i++) v[len[i]]++;
for(int i=1; i<=cnt; i++) ans[i] = len[i];
for(int i=1; i<=n; i++) v[i] += v[i-1];
for(int i=cnt; i>=1; i--) q[v[len[i]]--] = i;
}
};
SAM S;

void Check()
{
memset(L, 0, sizeof(L));
n = strlen(str+1);
int x = 1, record = 0;
for(int i=1; i<=n; i++)
{
int c = str[i]-'a'+1;
while(x && !a[x][c]) x = fa[x];
if(!x) {x = 1; record = 0; continue;}
record = min(record, len[x]) + 1;
x = a[x][c];
L[x] = max(L[x], record);
}

for(int i=cnt; i>=1; i--)
L[fa[q[i]]] = max(L[fa[q[i]]], L[q[i]]);
for(int i=1; i<=cnt; i++)
ans[i] = min(ans[i], L[i]);
}

int main()
{
T = get(); T --;
scanf("%s", str+1); n = strlen(str+1);
for(int i=1; i<=n; i++) S.Add(str[i]-'a'+1);
S.Pre();

while(T--)
{
scanf("%s", str+1);
Check();
}

for(int i=1; i<=cnt; i++)
Ans = max(Ans, ans[i]);

printf("%d",Ans);
}