多串的LCS,注意要利用拓扑序更新suf的len。
我用min,max,三目会超时，所以都改成了if,else
|
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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116 |
#pragma warning(disable:4996)#include<cstring>#include<string>#include<iostream>#include<cmath>#include<vector>#include<algorithm>#define maxn 100050using
namespace std;struct
State{ State *suf, *go[26]; int
val, len[2]; State() :suf(0), val(0){ memset(go, 0, sizeof(go)); memset(len, 0, sizeof(len)); }}*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; np->len[1] = np->val; 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->len[1] = nq->val; 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
str[maxn];int
n;int
bcnt[maxn];State *b[maxn * 2];int
main(){ n = 0; scanf("%s", str); init(); int
len = strlen(str); for
(int i = 0; i < len; i++){ extend(str[i] - ‘a‘); } int
tot = cur - root; memset(bcnt, 0, sizeof(bcnt)); for
(int i = 0; i < tot; i++) bcnt[statePool[i].val]++; for
(int i = 1; i <= len; i++) bcnt[i] += bcnt[i - 1]; for
(int i = tot - 1; i >= 0; i--) b[--bcnt[statePool[i].val]] = &statePool[i]; while
(scanf("%s", str) != EOF){ int
lenb = strlen(str); int
cnt = 0; State *p = root; for
(int i = 0; i < lenb; i++){ if
(p->go[str[i] - ‘a‘]){ cnt++; p = p->go[str[i] - ‘a‘]; } else{ while
(p&&!p->go[str[i] - ‘a‘]) p = p->suf; if
(!p) { p = root; cnt = 0; } else{ cnt = p->val + 1; p = p->go[str[i] - ‘a‘]; } } if
(cnt > p->len[0]){ p->len[0] = cnt; } } for
(int i = tot - 1; i >= 0; i--){ if
(b[i]->len[0]<b[i]->len[1]) b[i]->len[1] = b[i]->len[0]; if
(b[i]->suf&&b[i]->suf->len[0]< b[i]->len[0]){ b[i]->suf->len[0] = b[i]->len[0]; } b[i]->len[0] = 0; } } int
ans = 0; for
(int i = 0; i < tot; i++){ if
(ans < b[i]->len[1]){ ans = b[i]->len[1]; } } printf("%d\n", ans); return
0;} |
原文：http://www.cnblogs.com/chanme/p/3551762.html