人生第一道后缀自动机，总是值得纪念的嘛。。
后缀自动机学了很久很久，先是看CJL的论文，看懂了很多概念，关于right集，关于pre,关于自动机的术语，关于为什么它是线性的结点，线性的连边。许多铺垫的理论似懂非懂。然后看了下自动机的构造发现代码倒是挺简单，但是理解原理却是十分的困难，最后在网上找到一篇带例子的讲解帖子，我感觉算是能够说服我的吧放个链接：
http://blog.sina.com.cn/s/blog_70811e1a01014dkz.html
本题也是CLJ论文里的题，关键是如何求right集的大小，这里的求right集的大小我给个个人的理解，首先是按拓扑序吧，那三行for就有点像基数排序的姿势了，然后再由val大的算val小的。一开始令right++,是沿着root往下走的right 的初始大小，然后再按拓扑序往pre上加，就可以统计出每个状态的right集的大小了，姿势大致如此吧，代码完全参考了CLJ的论文和下面的这个链接：
http://blog.csdn.net/acm_cxlove/article/details/8222728
很感谢各位大神的分享，让我能够对后缀自动机有更深入的理解。
|
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 |
#pragma warning(disable:4996)#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<cmath>#include<vector>#define maxn 250050using
namespace std;struct
State{ State *suf, *go[26]; int
val, right; 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
str[maxn + 50];int
n;int
tot;int
dp[maxn + 50];int
cnt[maxn + 50];State *b[2 * maxn];int
main(){ while
(~scanf("%s", str)) { init(); n = strlen(str); for
(int i = 0; i < n; i++){ extend(str[i] - ‘a‘); } tot = cur - statePool; memset(cnt, 0, sizeof(cnt)); for
(int i = 0; i < tot; i++) cnt[statePool[i].val]++; for
(int i = 1; i <= n; i++) cnt[i] += cnt[i - 1]; for
(int i = 0; i < tot; i++) b[--cnt[statePool[i].val]] = &statePool[i]; for
(int i = 0; i < n; i++) { root = root->go[str[i] - ‘a‘]; root->right++; } memset(dp, 0, sizeof(dp)); for
(int i = tot - 1; i > 0; i--){ dp[b[i]->val] = max(dp[b[i]->val], b[i]->right); if
(b[i]->suf) b[i]->suf->right += b[i]->right; } for
(int i = n - 1; i >= 1; i--) dp[i] = max(dp[i], dp[i + 1]); for
(int i = 1; i <= n; i++) printf("%d\n", dp[i]); } return
0;} |
原文：http://www.cnblogs.com/chanme/p/3551035.html