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.
链接
SPOJ-1811
题解
题意：求两个字符串A,B的最长公共子串。字符串长度不超过 $250000$。
我们先构造 $A$ 的 $SAM$，然后用 $A$ 的 $SAM$ 一次读入 $B$ 的每一个字符，初始时状态在 $root$ 处，此时最大匹配数为 $0$，（这里的最大匹配数是指以当前读入的字符结尾，往前能匹配的最大长度），设当前到达的状态为 $p$，最大匹配数为 $res$，读入的字符为 $x$，若 $p->next[x]!=NULL$，则说明可从当前状态读入一个字符 $x$ 到达下一个状态，则 $res++,p=p->next[x]$,否则，找到 $p$ 的第一个祖先 $s$，$s->next[x]!=NULL$,若 $s$ 不存在，则说明以 $x$ 结尾的字符串无法和 $A$ 串的任何位置匹配，则设 $res=0,p=root$。否则，设 $res=s->res+1,p=s->next[x]$。我们求$res$ 所达到的最大值即为所求．
代码
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
|
#include <bits/stdc++.h>
namespace SuffixAutomation {
const int MAXN = 500010;
struct Node {
Node *fa, *next[26];
int max;
Node(int max = 0) : max(max), fa(NULL) {
}
Node(int max, Node *p) {
*this = *p, this->max = max;
}
inline void *operator new(size_t);
} pool[MAXN], *cur = pool, *root, *last;
inline void *Node::operator new(size_t) {
return cur++;
}
inline Node *extend(int c, Node *p) {
Node *np = new Node(p->max + 1);
while (p && !p->next[c]) p->next[c] = np, p = p->fa;
if (!p) {
np->fa = root;
} else {
Node *q = p->next[c];
if (p->max + 1 == q->max) {
np->fa = q;
} else {
Node *nq = new Node(p->max + 1, q);
q->fa = np->fa = nq;
while (p && p->next[c] == q) p->next[c] = nq, p = p->fa;
}
}
return np;
}
inline int work(char *s) {
register int res = 0;
register Node *p = root;
for (register int len = 0; *s; ++s) {
register int c = *s - 'a';
while (p && !p->next[c]) p = p->fa;
if (!p) p = root, len = 0;
else len = std::min(p->max, len) + 1, p = p->next[c];
res = std::max(res, len);
}
return res;
}
inline void solve() {
root = last = new Node();
static char s[MAXN];
scanf("%s", s);
for (register char *c = s; *c; c++) last = extend(*c - 'a', last);
scanf("%s", s);
std::cout << work(s);
}
}
int main() {
SuffixAutomation::solve();
return 0;
}
|
