【题解】SAM瞎做 · 字典序相关

为了证明自己不是🕊并且自己经常写博客,打算把本来可以 $1p$ 讲完的分了 $4p$。这是第二 $p$,嘎嘎嘎。

$1$ LG1368 工艺

似乎std是什么最小表示法,看⑧透啊,$O(n)$ 的SAM它不香吗 ?

把一个串循环排列,求最小的字典序排列。

发现把串向SAM里面插两次,从始状态开始不断找最小的转移,走 $n$ 次就完了。

似乎只是用到了一丢丢SAM的性质啊QAQ

$2$ [SP7258] Lexicographical Substring Search

题目名称…好长…

给定一个字符串,求本质不同排名第k小的子串。

考虑首先在SAM上算出现次数,然后从 $1$ 开始走,类似于二叉搜索木找 $k-$极值 的方式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void dfs2(int u){
if (vis[u]) return ; vis[u] = 1 ;
for (int i = 0 ; i < 26 ; ++ i)
if (S.trans[u][i])
dfs2(S.trans[u][i]),
g[u] += g[S.trans[u][i]] ;
}
void go_Out(int p, int s){
if (s <= f[p])
return ;
else s -= f[p] ;
for (int i = 0 ; i < 26 ; ++ i)
if (!S.trans[p][i]) continue ;
else if (s > g[S.trans[p][i]]) s -= g[S.trans[p][i]] ;
else { printf("%c", i + 'a'), go_Out(S.trans[p][i], s) ; return ; }
}
int main(){
cin >> (In + 1) >> T ;
N = strlen(In + 1) ; S.Init() ;
for (int i = 1 ; i <= N ; ++ i) S.Ins(In[i] - 'a') ;
for (int i = 2 ; i <= S.sz ; ++ i) add(S.fa[i], i) ;
for (int i = 2 ; i <= S.sz ; ++ i) g[i] = f[i] = 1 ;
dfs2(1) ; while (T --) K = qr(), go_Out(1, K), puts("") ;
}

$3$ [TJOI2015]弦论

求:

1、本质不同的第 $k$ 小子串。

2、第 $k$ 小子串。

发现第一问就是上面那一道,但是第二问里面,本质不同的串要算多次。

然而其实并没有什么变化,$dfs$ 一遍顺便算个出现次数就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void dfs(int u){
for (int k = head[u] ; k ; k = next(k))
dfs(to(k)), f[u] += f[to(k)] ;
}
void dfs2(int u){
if (vis[u]) return ; vis[u] = 1 ;
for (int i = 1 ; i <= 26 ; ++ i)
if (S.trans[u][i])
dfs2(S.trans[u][i]), g[u] += g[S.trans[u][i]] ;
}
void go_Out(int p, int s){
if (s <= f[p]) return ; else s -= f[p] ;
for (int i = 1 ; i <= 26 ; ++ i)
if (!S.trans[p][i]) continue ;
else if (s > g[S.trans[p][i]]) s -= g[S.trans[p][i]] ;
else { printf("%c", i + 'a' - 1), go_Out(S.trans[p][i], s) ; return ; }
}