SP1811-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.
输入格式:
The input contains exactly two lines, each line consists of no more than 250000 lowercase letters, representing a string.
输出格式:
The length of the longest common substring. If such string doesn’t exist, print “0” instead.
样例:
样例输入 1:
1
2
| alsdfkjfjkdsal
fdjskalajfkdsla
|
样例输出 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
| #include "ybwhead/ios.h"
using namespace std;
const int maxn = 1e6 + 10;
int nl;
struct SAM
{
struct node
{
int len, fa, mp[26];
} x[maxn];
int las, cnt;
SAM()
{
las = cnt = 1;
}
void insert(int c)
{
int p = las;
x[las = ++cnt] = {nl, 0, {0}};
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 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;
}
ans = max(ans, tot);
}
return ans;
}
} s;
string s1, s2;
int main()
{
yin >> s1 >> s2;
for (nl = 1; nl <= s1.size(); nl++)
s.insert(s1[nl - 1] - 'a');
yout << s.search(s2) << endl;
return 0;
}
|