发表更新OI笔记13 分钟读完 (大约1925个字)

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. 暂无来源

KMP学习笔记

https://big-news.cn/2020/08/31/KMP学习笔记/

作者

ce-amtic

发布于

2020-08-31

更新于

2020-12-27

许可协议

CC BY-NC-SA 4.0

#

评论

目录

推荐阅读

Your browser is out-of-date!

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

×

×