【题解】SAM瞎做 · 公共子串相关

为了水blog,决定单拿出来再整理一篇233

严格来讲,这东西似乎应该算在广义SAM的范畴?

$1$ SP1811 LCS

输入 $2$ 个长度不大于 $250000$ 的字符串,输出这 $2$ 个字符串的最长公共子串。

考虑对两个串一起建SAM,方法是插入一个串后随便插入一个 $\not\in \Sigma$ 的字符间隔开,这样,从本质上就把第二个串的后缀连成了一棵新子树接在虚根的下面。

还是原来的 $dp$ 原理。每次遇到一个在两个串中都出现过的串就把答案更新一下。

嗯,不得不说,SAM按照 $endpos$ 构建等价类这个想法实在太妙了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void dfs(int x){
for (int k = head[x] ; k ; k = next(k))
dfs(to(k)), f[x][0] += f[to(k)][0], f[x][1] += f[to(k)][1] ;
if (f[x][0] && f[x][1]) ans = max(ans, sam.len[x]) ;
}
int main(){
sam.Init() ;
cin >> (S + 1) >> (T + 1) ;
N = strlen(S + 1), M = strlen(T + 1) ;
for (int i = 1 ; i <= N ; ++ i) sam.Ins(S[i] - 'a' + 1, 0) ; sam.Ins(27, 0) ;
for (int i = 1 ; i <= M ; ++ i) sam.Ins(T[i] - 'a' + 1, 1) ;
for (int i = 2 ; i <= sam.sz ; ++ i) add(sam.fa[i], i) ; dfs(1) ;
cout << ans << endl ; return 0 ;
}

$2$ [HAOI2016] 找相同字符

给定两个字符串,求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两个子串中有一个位置不同。

我明白了,$15,16$ 年的时候正值SAM变的普及的阶段,所以这种没有新意的题才会有一堆人出。

首先就是乘法原理,然后考虑不同的子串数量可以直接 $parent$ 上父子差分,然后就没了。

1
2
3
4
5
6
void dfs(int x){
for (int k = head[x] ; k ; k = next(k))
dfs(to(k)), f[x][0] += f[to(k)][0], f[x][1] += f[to(k)][1] ;
if (x > 1 && f[x][0] && f[x][1])
ans += 1ll * f[x][0] * f[x][1] * (sam.len[x] - sam.len[sam.fa[x]]);
}

$3$ 多串的LCS

此处的 “S” 指的是 “Substring” 的意思啦。

本质上是SPOJ的两道题,SP10570 LONGCSSP1812 LCS2

给定一些字符串,求出它们的最长公共子串

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
char S[MAXN], T[MAXN] ;
int N, L, res, ans[MAXN] ;
struct SAM{
int last, sz ;
int fa[MAXN], f[MAXN], len[MAXN] ;
int trans[MAXN][27], buc[MAXN], base[MAXN] ;
void Init(){
last = sz = 1 ;
memset(f, 63, sizeof(f)) ;
}
void Insert(int x){
int p = last, np = ++ sz ;
last = np, len[np] = len[p] + 1 ;
while (p && !trans[p][x])
trans[p][x] = np, p = fa[p] ;
if (!p)
return fa[np] = 1, void() ;
int q = trans[p][x] ;
if (len[q] == len[p] + 1)
return fa[np] = q, void() ;
int nq = ++ sz ;
fa[nq] = fa[q],
fa[q] = fa[np] = nq ;
len[nq] = len[p] + 1 ;
memcpy(trans[nq], trans[q], sizeof(trans[q])) ;
while (p && trans[p][x] == q)
trans[p][x] = nq, p = fa[p] ;
}/*
void dfs(int x){
if (vis[x]) return ; vis[x] = 1 ;
for (int i = 1 ; i <= 26 ; ++ i) if (trans[x][i]) dfs(trans[x][i]) ;
ans[fa[x]] = max(ans[fa[x]], min(ans[x], len[fa[x]])) ;
f[x] = min(f[x], ans[x]), ans[x] = 0 ;
}*/
void sort(){
for (int i = 1 ; i <= sz ; ++ i) buc[len[i]] ++ ;
for (int i = 1 ; i <= sz ; ++ i) buc[i] += buc[i - 1] ;
for (int i = sz ; i >= 1 ; -- i) base[buc[len[i]] --] = i ;
}
void work(char * s){
int rt = 1, x, l = 0 ;
for (int i = 1 ; i <= L ; ++ i){
x = s[i] - 'a' + 1 ;
while (rt && !trans[rt][x]) rt = fa[rt], l = len[rt] ;
if (rt) ++ l, rt = trans[rt][x], ans[rt] = max(ans[rt], l) ;
else rt = 1, l = 0 ;
}
for (int i = sz ; i ; -- i)
rt = base[i], x = fa[rt],
ans[x] = max(ans[x], min(ans[rt], len[x])),
f[rt] = min(f[rt], ans[rt]), ans[rt] = 0 ;
// for (int i = 1 ; i <= sz ; ++ i) cout << ans[i] << " " ; puts("") ;
// dfs(1) ;
}
}M ;

int main(){
scanf("%s", S + 1) ; int i ;
N = strlen(S + 1), M.Init() ;
for (i = 1 ; i <= N ; ++ i)
M.Insert(S[i] - 'a' + 1) ;
M.sort() ;
while (~scanf("%s", T + 1))
L = strlen(T + 1), M.work(T) ;
for (i = 1 ; i <= M.sz ; ++ i)
res = max(res, M.f[i]) ;
cout << res << endl ;
}

首先拿第一个串朴素建 SAM。对于一个新的串,考虑将这个串放到 SAM 上运行,同时记录每个位置能够匹配到的最长长度。再用一个 $f$ 记录全局,而 $f$ 显然应该对每个串的 $rt$ 处的匹配取 $\min$。

嗯,注意由于 $parent$ 树的性质,父亲答案的一部分包含在儿子中,但也不会多于自身的长度。于是一开四$topsort$ 一遍就可以了。复杂度似乎是 $\sum\rm |S_i|$ ?

en,似乎这道题也是 [POI2000]公共串 的加强版。不过这种题目几倍经验也不奇怪吧?

$4$ [SDOI2008] Sandy的卡片

Sandy和Sue的热衷于收集干脆面中的卡片。

每一张卡片都由一些数字进行标记,第 $i$ 张卡片的序列长度为 $M_i$,要想兑换人物模型,首先必须要集够 $N$ 张卡片,对于这 $N$ 张卡片,如果他们都有一个相同的子串长度为 $k$,则可以兑换一个等级为 $k$ 的人物模型。相同的定义为:两个子串长度相同且一个串的全部元素加上一个数就会变成另一个串。

现在又一堆卡片,请你帮助Sandy和Sue,看看他们最高能够得到哪个等级的人物模型。

看到这题蒙了半天,甚至写了一发枚举「加上的数是多少」然后再去SAM,结果发现原来不同串之间可以用不同的数 ……我是弟弟。

于是最后被题解暴击:差分一下即可。我是dd。QAQ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int main(){
cin >> T >> N ; T -- ; int i, j ;
for (i = 1 ; i <= N ; ++ i) scanf("%d", &S[i]) ;
for (i = 1 ; i <= N ; ++ i) t[i] = S[i] - S[i - 1] ; M.Init() ;
for (i = 1 ; i <= N ; ++ i) M.Insert(t[i]) ; M.sort() ;
for (i = 1 ; i <= T ; ++ i){
scanf("%d", &ss[i][0]) ;
for (j = 1 ; j <= ss[i][0] ; ++ j) scanf("%d", &ss[i][j]);
for (j = 2 ; j <= ss[i][0] ; ++ j) t[j] = ss[i][j] - ss[i][j - 1] ;
// for (j = 1 ; j <= ss[i][0] ; ++ j) cout << t[j] << " " ; puts(" ") ;
t[1] = -(i + 1) ; M.work(t, ss[i][0]) ;
}
for (i = 1 ; i <= M.sz ; ++ i) res = max(res, M.f[i]) ;
cout << res + 1 << endl ; return 0 ;
}

这个地方我默认把第一个元素瞎给了个值。

哦,还有,可能好久没写差分了?一开始写差分我是这么写的:

1
for (i = 1 ; i <= N ; ++ i) S[i] = S[i] - S[i - 1] ;

是弟中弟本弟没错了(cry