用后缀自动机求两个长串的最长公共子串，效果拔群。多样例的时候memset要去掉。
解题思路就是跟CLJ的一模一样啦。
|
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 |
#pragma warning(disable:4996)#include<cstring>#include<string>#include<iostream>#include<cmath>#include<vector>#include<algorithm>#define maxn 250050using
namespace std;struct
State{ State *suf, *go[26]; int
val; State() :suf(0), val(0){ memset(go, 0, sizeof(go)); }}*root, *last;State statePool[maxn * 2], *cur;void
init(){ cur = statePool; root = last = cur++;}void
extend(int
w){ State *p = last, *np = cur++; np->val = p->val + 1; while
(p&&!p->go[w]) p->go[w] = np, p = p->suf; if
(!p) np->suf = root; else{ State *q = p->go[w]; if
(p->val + 1 == q->val){ np->suf = q; } else{ State *nq = cur++; memcpy(nq->go, q->go, sizeof
q->go); nq->val = p->val + 1; nq->suf = q->suf; q->suf = nq; np->suf = nq; while
(p&&p->go[w] == q){ p->go[w] = nq, p = p->suf; } } } last = np;}char
stra[maxn], strb[maxn];int
main(){ while
(~scanf("%s%s", stra, strb)) { init(); //memset(statePool, 0, sizeof(statePool)); int
lena = strlen(stra); for
(int i = 0; i < lena; i++){ extend(stra[i] - ‘a‘); } int
ans = 0; int
lenb = strlen(strb); State *p = root; int
len = 0; for
(int i = 0; i < lenb; i++){ if
(p->go[strb[i] - ‘a‘]){ len++; ans = max(ans, len); p = p->go[strb[i] - ‘a‘]; } else{ while
(p&&!p->go[strb[i] - ‘a‘]){ p = p->suf; } if
(!p) { p = root; len = 0; } else{ len = p->val + 1; ans = max(len, ans); p = p->go[strb[i] - ‘a‘]; } } } printf("%d\n", ans); } return
0;} |
原文：http://www.cnblogs.com/chanme/p/3551560.html