KMP学习笔记

众所周知,对于一般的字符串题,存在如下规律:字符串算法 < hash < 暴力,其中 “<” 代表“劣于”。

kmp 被用来解决下面的这样一个问题:

给定两个字符串 $S,T$ ,求 $S$ 在 $T$ 中匹配的数量和位置。
$|T|,|S|\le 10^6$

直接 hash 和 kmp 都是 $O(|S|+|T|)$ 的复杂度,但是 kmp 的思想还是要理解的。
kmp 的思想基于下面这两个东西。

border

一个 border 定义为字符串的一段前缀,使其等于本串的一段后缀。
用符号表示的话就是找到一个 $k$,使得 $s[1:k]=s[n-k+1:n]$。容易发现我们可以用这个 $k$ 去双射一个 border。
众所周知,border 具有一个非常优美的性质,即你的 border 的 border 还是你的 border。

next[] 数组

定义 $nxt[i]=md(s[1:i])$ 是串 $s$ 的 $nxt[]$ 数组,其中 $md(x)$ 代表串 $x$ 的最长 border 长度(不能是自身)。
容易发现 $nxt[i], nxt[nxt[i]],…$ 构成了串 $s[1:i]$ 的所有 border。

kmp 每次确定一个最大的 $k$,使得 $S[1:k] = T[i - k + 1:i]$,然后尝试扩展 $k\to k+1$,如果 $k=|S|$ 则发现了匹配位置。
容易发现,这个尝试扩展的过程可以通过 border 来加速,即若 $S[k+1]\neq T[i+1]$,则令 $k=nxt[k]$ 即可。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const int CN = 1e6 + 6;

int n, m, nxt[CN]; char s[CN], t[CN];
cin >> (t + 1) >> (s + 1); n = strlen(t + 1), m = strlen(s + 1);

int k = 0; nxt[1] = 0, nxt[0] = -1; // k : 当前的最长 border
for(int i = 2; i <= m; i++){
while(k ^ -1 && s[k + 1] != s[i]) k = nxt[k]; // 去找次长 border
nxt[i] = (k += 1); // 往下匹配一位
}

k = 0;
for(int i = 1; i <= n; i++){
while(k ^ -1 && s[k + 1] != t[i]) k = nxt[k]; // 同理
if((k += 1) == m) printf("%d", i - m + 1), puts(""); // 已经匹配上
}

一道栗题

给定字符串 $S$,求 $S$ 的所有前缀的不重叠的 border 数量。
$|S|\le 5\times 10^7$

直接在 kmp 上维护即可,注意一下 kmp 想要保证复杂度则必须避免反复横跳。
时间复杂度 $O(n)$。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const int CN = 1e7 + 7;
const int P = 1e9 + 7;

int t, n, nxt[CN], num[CN]; char s[CN];
scanf("%s", s + 1); n = strlen(s + 1);

int k = 0; nxt[0] = -1, nxt[1] = 0, num[1] = 1;
for(int i = 2; i <= n; i++){
while(k ^ -1 && s[k + 1] != s[i]) k = nxt[k];
k += 1, nxt[i] = k, num[i] = num[k] + 1;
}

int ans = 1; k = 0;
for(int i = 2; i <= n; i++){
while(k ^ -1 && s[k + 1] != s[i]) k = nxt[k];
while(k > i / 2) k = nxt[k]; // 跑过了就挪回去
ans = 1ll * ans * (num[k] + 1) % P;
}

printf("%d", ans), puts("");

在字典树上的扩展

考虑这样一个问题:

给定一个字符串 $T$,和一些字符串 $S_1,S_2,…S_n$,对每个 $S_i$ 求其在 $T$ 中匹配的数量。
$|T|,\sum|S_i|\le 10^6$

解决方法是对 $S_i$ 建立字典树,然后再在字典树上建立类似于 $nxt[]$ 指针的结构。注意到这种方法具有可扩展性,即广义后缀自动机也通过类似的思想构建。

于是这棵字典树变成了一个确定有限状态自动机(DFA),我们称其为 AC自动机(Aho-Corasick Automaton, ACAM)

则可以得到这样一份构建代码:

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
const int CN = 1e6 + 6;
class ACAM {
public: int son[CN][26], fail[CN], e[CN], idx; queue<int> Q;
void ins(char *s){
int u = 0;
for(int i = 0; s[i]; i++){
if(!son[u][ s[i] - 'a' ]) son[u][ s[i] - 'a' ] = ++idx;
u = son[u][ s[i] - 'a' ];
}
e[u]++;
}
void bd(){
for(int i = 0; i < 26; i++) if(son[0][i]) Q.push( son[0][i] );
while(!Q.empty()){
int u = Q.front(); Q.pop();
for(int i = 0; i < 26; i++)
if(son[u][i]) fail[ son[u][i] ] = son[ fail[u] ][i], Q.push(son[u][i]);
else son[u][i] = son[ fail[u] ][i];
}
}
int qu(char *s){
int u = 0, r = 0;
for(int i = 0; s[i]; i++){
u = son[u][ s[i] - 'a' ];
for(int j = u; j && e[j] ^ -1; j = fail[j])
r += e[j], e[j] = -1;
}
return r;
}
} D;

又一道栗题

给定一个字符串 $T$ 和一些字符串 $S_1,S_2,…S_n$,定义一个字符串是可爱的当且仅当它不包含任何 $S_i$ 作为子串。试删除最少的字符使得 $T$ 变得可爱。
$|T|,\sum|S_i|\le 5000$

考虑 DP,设 $f[l,u]$ 为考虑 $S[1:l]$,在AC自动机上走到了节点 $u$ 的最小代价。考虑 $S[l+1]$ 是否删除,则有转移:
$$\begin{aligned} &f[l,u]+1\to f[l + 1, u]\newline &f[l,u]\to f[l+1,v] \text{ }|\text{ }son[u, S[l + 1]] = v\end{aligned}$$ $v$ 点应当满足怎样的限制呢?首先它不应该是接受状态,并且 fail 树上它到根的路径上也不能存在接受状态,因为这些状态是后缀等价的。那么按照 bfs 序更新一下即可,时间复杂度 $O(|T|\sum |S_i|)$。

代码:

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
const int CN = 2020;
class ACAM {
public: int son[CN][26], fail[CN], w[CN], idx; queue<int> Q;
void ins(char *s){
int u = 0;
for(int i = 0; s[i]; i++){
if(!son[u][ s[i] - 'a' ]) son[u][ s[i] - 'a' ] = ++idx;
u = son[u][ s[i] - 'a' ];
}
w[u]++;
}
void bd(){
for(int i = 0; i < 26; i++) if(son[0][i]) Q.push(son[0][i]);
while(!Q.empty()){
int u = Q.front(); Q.pop();
for(int i = 0; i < 26; i++)
if(son[u][i]) fail[ son[u][i] ] = son[ fail[u] ][i], Q.push(son[u][i]);
else son[u][i] = son[ fail[u] ][i];
w[u] += w[ fail[u] ]; // mark
}
}
int f[CN][CN];
int solve(char *s, int n){
memset(f, 0x3f, sizeof(f)), f[0][0] = 0;
for(int l = 0; l < n; l++)
for(int i = 0; i <= idx; i++){
f[l + 1][i] = min(f[l + 1][i], f[l][i] + 1);
int v = son[i][ s[l] - 'a' ];
if(!w[v]) f[l + 1][v] = min(f[l + 1][v], f[l][i]);
}
int ans = 0x3f3f3f3f;
for(int i = 0; i <= idx; i++) ans = min(ans, f[n][i]);
return ans;
}
} D;

双一道栗题

给定一些字符串 $S_1,S_2,…S_n$ 和字符集 $\Sigma$,每个字符串 $S_i$ 有一个价值 $w_i$。
定义一个字符串的价值为其所有子串的价值和(未定义则为 $0$),求一个长度为 $l$ 的串使得其价值最大。
$|\Sigma|\le 26 ,\sum|S_i|,l\le 1000$

考虑 DP,假设当前的字符串为 $s$,新增了一个字符 $c$ 得到 $sc$,则新增的子串应当是 $sc$ 的所有后缀,新增字符的价值为这些后缀的价值和。
对 $S_i$ 建立AC自动机,则“这些后缀的价值和”体现为 fail 树上从根到 $sc$ 所在的节点的权值和,我们记其为 $w[u]$。

于是就可以 DP 了,设 $f[l,u]$ 表示当前拼出的串长度为 $l$,现在在AC自动机上的节点 $u$ 的最大价值,有转移:
$$ f[l,u]+w[v]\to f[l+1,v]\text{ }|\text{ }\exists c, \text{s.t.} son[u, c]=v$$ 时间复杂度 $O(l\sum|S_i||\Sigma|)$。

代码:

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 CN = 2020;

template < class T >
class queue { // 惨痛经历
public: T a[CN], hd, tl; queue() {hd = tl = 0;}
bool empty() {return hd ^ tl ? 0 : 1;}
T front() {return a[hd];}
void pop() {hd++;}
void push(int x) {a[tl++] = x;}
} ;

class ACAM {
public: int w[CN], son[CN][26], fail[CN], idx; queue<int> Q;
void ins(char *s, int val){
int u = 0;
for(int i = 0; s[i]; i++){
if(!son[u][ s[i] - 'a' ]) son[u][ s[i] - 'a' ] = ++idx;
u = son[u][ s[i] - 'a' ];
}
w[u] += val;
}
void bd(){
for(int i = 0; i < 26; i++) if(son[0][i]) Q.push(son[0][i]);
while(!Q.empty()){
int u = Q.front(); Q.pop();
for(int i = 0; i < 26; i++)
if(son[u][i]) fail[ son[u][i] ] = son[ fail[u] ][i], Q.push(son[u][i]);
else son[u][i] = son[ fail[u] ][i];
w[u] += w[ fail[u] ]; // mark
}
}
int f[CN][CN];
int solve(int l){
memset(f, -0x3f, sizeof(f)), f[0][0] = 0;
for(int i = 0; i < l; i++)
for(int u = 0; u <= idx; u++)
for(int c = 0; c < 26; c++)
f[i + 1][ son[u][c] ] = max(f[i + 1][ son[u][c] ], f[i][u] + w[ son[u][c] ]);
int ans = -0x3f3f3f3f;
for(int u = 0; u <= idx; u++) ans = max(ans, f[l][u]);
return ans;
}
} D;

相关题目

  1. 「NOI2014」动物园
  2. 暂无来源
  3. 暂无来源
  4. 暂无来源

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×