再论后缀自动机

在之前已经对后缀自动机的概念进行了阐述
后缀数组与后缀自动机

其实这种思想有很多应用
对这个算法的构造和思考如下

后缀自动机构造原理

sam1
sam2
sam3
sam4
sam5
sam6

LCS问题的O(nlogn)解法

HDU1159
HDU1159
HDU1159-02

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
const int maxn = 1000 + 5;
char A[maxn], B[maxn];

vector<int> loc[maxn];
vector<int> C, D;

void init() {
_for(i, 0, maxn) loc[i].clear();
C.clear();
D.clear();
}

int main() {
freopen("input.txt", "r", stdin);
while (scanf("%s%s", A, B) != EOF) {
init();

int lenA = strlen(A), lenB = strlen(B);


_forDown(i, lenB - 1, 0) loc[B[i] - 'a'].push_back(i);
_for(i, 0, lenA) {
int x = A[i] - 'a';
if(loc[x].empty()) continue;
_for(j, 0, loc[x].size()) {
C.push_back(loc[x][j]);
}
}

if(!C.empty()) {
D.push_back(C[0]);
_for(i, 1, C.size()) {
if(C[i] > D.back()) D.push_back(C[i]);
else {
vii it = lower_bound(D.begin(), D.end(), C[i]);
*it = C[i];
}
}
}

cout << D.size() << endl;
}
}

LCS问题的O(n)算法

LCS

LCS

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
const int maxl = 250005;
const int maxn = maxl * 2;


class SAM {
public:
int sz, last;
int trans[maxn][26], link[maxn], maxlen[maxn];

SAM() {
Set(trans, 0);
Set(link, 0);
Set(maxlen, 0);

sz = last = 1;
}

void extend(int ch) {
int cur = ++sz, p = last;
maxlen[cur] = maxlen[p] + 1;

for( ; p && trans[p][ch] == 0; p = link[p]) trans[p][ch] = cur;

if(p == 0) link[cur] = 1;
else {
int q = trans[p][ch];
if(maxlen[p] + 1 == maxlen[q]) link[cur] = q;
else {
int clone = ++sz;
maxlen[clone] = maxlen[p] + 1;

Cpy(trans[clone], trans[q]);
link[clone] = link[q];

for( ; p && trans[p][ch] == q; p = link[p]) trans[p][ch] = clone;
link[q] = link[cur] = clone;
}
}

last = cur;
}

int LCS(const char* str) {
int len = strlen(str);
int lcs = 0, tmplen = 0;
int cur = 1;

_for(i, 0, len) {
int x = str[i] - 'a';
if(trans[cur][x]) {
cur = trans[cur][x];
tmplen++;
}
else {
while (cur && trans[cur][x] == 0) cur = link[cur];
if(cur) {
tmplen = maxlen[cur] + 1;
cur = trans[cur][x];
}
else {
tmplen = 0;
cur = 1;
}
}
lcs = max(lcs, tmplen);
}
return lcs;
}
};

SAM sam;

int main() {
freopen("input.txt", "r", stdin);
char A[maxl], B[maxl];
scanf("%s%s", A, B);
int lenA = strlen(A), lenB = strlen(B);

_for(i, 0, lenA) sam.extend(A[i] - 'a');
cout << sam.LCS(B) << endl;

}

SAM根据maxlen对节点排序

SAMRadix

SAM求子串出现次数

子串的长度为k
比如ababa, 有很多长度为3的子串
其中’aba’出现2次, ‘bab’出现1次

求长度为k的子串
最多可能出现多少次?

SAMSubstr

Substrings

SAM和拓扑排序(BFS版本)

这种写法会超时

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
SAM sam;

vector<int> G[maxn];
int indeg[maxn];
llong ans[maxn];

void init() {
Set(cnt, 0);
Set(ans, 0);
Set(indeg, 0);
}

void build() {
_rep(i, 1, sam.sz) {
G[i].push_back(sam.link[i]);
indeg[sam.link[i]]++;
}
}

void topo() {
queue<int> que;
_rep(i, 0, sam.sz) if(indeg[i] == 0) que.push(i);

while (!que.empty()) {
int u = que.front();
que.pop();

_for(i, 0, G[u].size()) {
int v = G[u][i];
cnt[v] += cnt[u];

if(--indeg[v] == 0) que.push(v);
}
}

_rep(i, 1, sam.sz) ans[sam.maxlen[i]] = max(ans[sam.maxlen[i]], cnt[i]);
}

// usage: build() topo()

int main() {
freopen("input.txt", "r", stdin);
init();

char str[maxl];
scanf("%s", str);
int len = strlen(str);

_for(i, 0, len) sam.extend(str[i] - 'a');

build();
topo();
_forDown(i, len, 1) ans[i] = max(ans[i], ans[i + 1]);
_rep(i, 1, len) cout << ans[i] << endl;
}

用RadixSort优化拓扑排序

从小到大的排序, 按照maxlen的排名
maxlen从[0, len], 序号依次是{1, 2, …, sam.sz}

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
const int maxl = 250000 + 5;
const int maxn = maxl * 2;

llong cnt[maxn];
int len;

class SAM {
public:
int maxlen[maxn], link[maxn], trans[maxn][26];
int last, sz;

SAM() {
Set(maxlen, 0);
Set(link, 0);
Set(trans, 0);

last = sz = 1;
}

void extend(int ch) {
int cur = ++sz, p = last;
maxlen[cur] = maxlen[p] + 1;
cnt[cur] = 1;

for( ; p && trans[p][ch] == 0; p = link[p]) trans[p][ch] = cur;

if(p == 0) link[cur] = 1;
else {
int q = trans[p][ch];
if(maxlen[q] == maxlen[p] + 1) link[cur] = q;
else {
int clone = ++sz;
maxlen[clone] = maxlen[p] + 1;

Cpy(trans[clone], trans[q]);
link[clone] = link[q];

for(; p && trans[p][ch] == q; p = link[p]) trans[p][ch] = clone;
link[q] = link[cur] = clone;
}
}

last = cur;
}
};

SAM sam;

// use Radix sort instead of bfs-topoSort


int C[maxn];
int id[maxn];
llong ans[maxn];

void init() {
Set(cnt, 0);
Set(C, 0);
Set(id, 0);
Set(ans, 0);
}

void rsort() {
Set(C, 0);
_rep(i, 1, sam.sz) C[sam.maxlen[i]]++;
_rep(i, 1, len) C[i] += C[i - 1];
_forDown(i, sam.sz, 1) id[C[sam.maxlen[i]]--] = i;

_forDown(i, sam.sz, 1) {
int u = id[i];
cnt[sam.link[u]] += cnt[u];
}
}

void solve() {
_rep(i, 1, sam.sz) ans[sam.maxlen[i]] = max(ans[sam.maxlen[i]], cnt[i]);
_forDown(i, len, 1) ans[i] = max(ans[i], ans[i + 1]);
}

int main() {
freopen("input.txt", "r", stdin);
init();

char str[maxl];
scanf("%s", str);
len = strlen(str);

_for(i, 0, len) sam.extend(str[i] - 'a');

rsort();
solve();
_rep(i, 1, len) printf("%d\n", ans[i]);

}

值得注意的是
cnt[suffix]随着len的增加, 是递减的
所以刷cnt[i]的值的时候, 从大的len往小的len刷

1
2
3
4
5
for(int i = sam.sz; i >= 1; i--) {
// 找到排名最靠后的点, 也就是len最长的点
int u = id[i];
cnt[sam.link[u]] += cnt[u];
}

endpos()性质

endpos1
endpos2
endpos3
endpos4
endpos5