后缀自动机的应用

后缀自动机的应用

求两个字符串的最长公共子串

SPOJ1811 Longest Common Substring

方法:

对于AA字符串建SAMSAM,考虑BB串从头到尾枚举。假设枚举到第ii位。

xx表示当前(到第i1i-1位)在SAMSAM走到的节点,ll表示当前匹配的以字符cc(bb串的第ii个字符)结尾的子串中最大的长度。

chx,c=0ch_{x,c}=0,则x=faxx=fa_x直到xx00

否则,x=chx,cx=ch_{x,c}l=l+1l=l+1此时满足xx到根节点11的路径上的所有点,都是合法的子串。显然最大的就是ll。跟答案取大就行了。

1
2
3
4
5
6
7
8
9
10
11
int ans = 0, n = strlen(s + 1), now = 0, p = 1;
for(int i = 1; i <= n; ++i) {
int c = s[i] - 'a';
if(ch[p][c]) p = ch[p][c], ++now;
else {
while(p && !ch[p][c]) p = fa[p];
if(!p) now = 0;
else now = len[p] + 1, p = ch[p][c];
}
ans = max(ans, now);
}

求多个串的最长公共子串

SPOJ1812 Longest Common Substring II

方法:

对第一个串建SAMSAM。然后对于剩下的串,都从头到尾遍历一遍。按照前一题的思路,

假设枚举到第ii位。

xx表示当前(到第i1i-1位)在SAMSAM走到的节点,ll表示当前匹配的以字符cc(bb串的第ii个字符)结尾的子串中最大的长度。

chx,c=0ch_{x,c}=0,则x=faxx=fa_x直到xx00

否则,x=chx,cx=ch_{x,c}l=l+1l=l+1此时满足xx到根节点11的路径上的所有点,都是合法的子串。

然后每个节点取子树里的最大值,然后取自己和这个最大值的最小值。

对于每个节点与答案取最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
memset(f, 0, sizeof f);
for(int i = 1; i <= n; ++i) {
int c = s[i] - 'a';
if(ch[p][c]) p = ch[p][c], ++now;
else {
while(p && !ch[p][c]) p = fa[p];
if(!p) now = 0;
else now = len[p] + 1, p = ch[p][c];
}
f[p] = max(f[p], now);
}
for(int i = cnt; i >= 1; --i) {
int q = fa[a[i]];
f[q] = max(f[q], f[a[i]]);
f[a[i]] = min(f[a[i]], len[a[i]]);
g[a[i]] = min(g[a[i]], f[a[i]]);
}
int ans = 0;
for(int i = 1; i <= cnt; ++i) ans = max(ans, g[i]);

求循环同构在主串里的出现次数

CF235C Cyclical Quest

方法:

对主串SSSAMSAM

按照上面两题的思路,xx表示匹配到的SAMSAM上的节点。

go(c)go(c)表示在当前匹配的字符串末尾加上字符cc

del()del()表示删除当前匹配的字符串的首字符

cal()cal()计算答案。

具体细节直接看代码:

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
void go(int c) {
while(x && !ch[x][c]) l = len[x = fa[x]];
if(ch[x][c]) {
x = ch[x][c];
++l;
}
}
void cal() {
if(l == n && vis[x] < TT) {
ans += siz[x];
vis[x] = TT;
}
}
void del() {
if(l > n && (--l == len[fa[x]])) x = fa[x];
}
void solve() {
ans = 0;
scanf("%s", s +1);
n = strlen(s +1);
x = 1;
l = 0;
for(int i = 1; i <= n; ++i) go(s[i] - 'a');
cal();
for(int i = 1; i < n; ++i) {
go(s[i] - 'a');
del();
cal();
}
printf("%d\n", ans);
}

本质不同的子串个数

BZOJ4516 [Sdoi2016]生成魔咒

方法:

每加一个字符,显然只会增加lennplenfa[np]len_{np}-len_{fa[np]}个不同子串,直接算答案。

求排名第kk小的子串

SPOJ7258 SUBLEX

BZOJ3998 [TJOI2015]弦论

方法:

按照trietrie树遍历的类似思路,假设当前遍历到节点xx,从az枚举转移,如果sumyksum_y\ge k,则进入这个子树,否则k=ksumyk=k-sum_y

直到走到k0k\leq 0退出即可。