SP1812-LCS2 - Longest Common Substring II
题目:
题目描述:
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.
输入格式:
The input contains at most 10 lines, each line consists of no more than 100000 lowercase letters, representing a string.
输出格式:
The length of the longest common substring. If such string doesn’t exist, print “0” instead.
样例:
样例输入 1:
1
2
3
| alsdfkjfjkdsal
fdjskalajfkdsla
aaaajfaaaa
|
样例输出 1:
思路:
实现:
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 "ybwhead/ios.h"
using namespace std;
const int maxn = 1e6 + 10;
int nl;
struct SAM
{
struct node
{
int len, fa, mp[26], mx, mi;
} x[maxn];
int las, cnt;
SAM()
{
las = cnt = 1;
}
void insert(int c)
{
int p = las;
x[las = ++cnt] = {nl, 0, {0}, 0, INT_MAX};
for (; p && !x[p].mp[c]; p = x[p].fa)
x[p].mp[c] = las;
if (!p)
{
x[las].fa = 1;
return;
}
int q = x[p].mp[c];
if (x[q].len == x[p].len + 1)
{
x[las].fa = q;
return;
}
x[++cnt] = x[q];
x[cnt].len = x[p].len + 1;
x[q].fa = x[las].fa = cnt;
for (; x[p].mp[c] == q; p = x[p].fa)
x[p].mp[c] = cnt;
}
int a[maxn];
void search(string s)
{
int ans = 0, p = 1, tot = 0;
for (int i = 0; i < s.size(); i++)
{
if (x[p].mp[s[i] - 'a'])
{
++tot;
p = x[p].mp[s[i] - 'a'];
}
else
{
for (; p && !x[p].mp[s[i] - 'a']; p = x[p].fa)
;
if (p)
tot = x[p].len + 1, p = x[p].mp[s[i] - 'a'];
else
p = 1, tot = 0;
}
x[p].mx = max(x[p].mx, tot);
}
for (int i = 1; i <= cnt; i++)
{
int p = a[i];
x[x[p].fa].mx = max(x[x[p].fa].mx, min(x[p].mx, x[x[p].fa].len));
x[p].mi = min(x[p].mi, x[p].mx);
x[p].mx = 0;
}
}
} s;
string s1;
int cmp(int a, int b)
{
return s.x[a].len > s.x[b].len;
}
int main()
{
yin >> s1;
for (nl = 1; nl <= s1.size(); nl++)
s.insert(s1[nl - 1] - 'a');
for (int i = 1; i <= s.cnt; i++)
s.a[i] = i;
sort(s.a + 1, s.a + s.cnt + 1, cmp);
while (cin >> s1)
{
if (!s1.size())
break;
// yout << s1 << endl;
s.search(s1);
}
int ans = 0;
for (int i = 1; i <= s.cnt; i++)
ans = max(ans, s.x[i].mi);
yout << ans << endl;
return 0;
}
|