玖的数学&算法录
0%

算法笔记（06）：KMP

发表于 更新于
本文字数： 5.5k 阅读时长 ≈ 5 分钟

kmp

注意：next数组不要用next命名（可能和关键字重复）。

简单介绍：

字符串匹配问题：字符串 s 中查找某个字符串 p 是否出现

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
const int MAXN = 2e5 + 10;
int n,m;
int nxt[MAXN],f[MAXN];
char s[MAXN],p[MAXN];
//kmp head

void kmp() {
    n = strlen(s + 1);
    m = strlen(p + 1);
    int j = 0;
    nxt[1] = 0;
    for(int i = 2; i <= m; i++) {
        while(j > 0 && p[j + 1] != p[i]) 
            j = nxt[j];
        if(p[j + 1] == p[i])
            j++;
        nxt[i] = j;
    }

    j = 0;
    //回退
    for(int i = 1; i <= n; i++) {
        while((j == m) || (j > 0 && p[j + 1] != s[i]))
            j = nxt[j];
        if(p[j + 1] == s[i])
            j++;
        f[i] = j;
    }
}


时间复杂度

O（n + m)

Question 1: KMP板子题

给你两个字符串 a,b，字符串均由小写字母组成，现在问你 b 在 a 中出现了几次。

题解：很裸。

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
const int MAXN = 2e5 + 10;
int n,m;
int nxt[MAXN],f[MAXN];
char s[MAXN],p[MAXN];
//kmp head

void kmp() {
    //算nxt
    n = strlen(s + 1);
    m = strlen(p + 1);
    int j = 0;
    nxt[1] = 0;
    for(int i = 2; i <= m; i++) {
        while(j > 0 && p[j + 1] != p[i]) 
            j = nxt[j];
        if(p[j + 1] == p[i])
            j++;
        nxt[i] = j;
    }

    j = 0;
    //回退 算f
    for(int i = 1; i <= n; i++) {
        while((j == m) || (j > 0 && p[j + 1] != s[i]))
            j = nxt[j];
        if(p[j + 1] == s[i])
            j++;
        f[i] = j;
    }

    int ans = 0;
    for(int i=1;i<=n;i++) {
        if(f[i] == m) ++ans;
    }
    if(!ans) {
        std::cout << -1 << endl;
        std::cout << -1 << endl;
    } else {
        std::cout << ans << endl;
        for(int i=1;i<=n;i++) {
            if(f[i] == m)
                std::cout << i - m + 1 << " ";
        }
        std::cout << endl;
    }
}


void JiuCherish(){
    std::cin >> s + 1 >> p + 1;
    kmp();
}
Question 2:最小循环覆盖

给你一个字符串 a，你需要求出这个字符串的最小循环覆盖的长度。

b 是 a 的最小循环覆盖，当且仅当 a 是通过 b 复制多次并连接后得到的字符串的前缀，且 b 是满足条件的字符串中长度最小的。

输入一个字符串 a，输出一个数表示最小循环覆盖 b 的长度。

题解：

简单来说就是找任意一段字符，然后后面每一段字符和你找的字符是相同的。

妙妙结论题：找到的长度其实就是 m - nxt[m];

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
int n,m;
int nxt[MAXN],f[MAXN];
char s[MAXN],p[MAXN];
//kmp head

void kmp() {
    //算nxt
    n = strlen(s + 1);
    m = strlen(p + 1);
    int j = 0;
    nxt[1] = 0;
    for(int i = 2; i <= m; i++) {
        while(j > 0 && p[j + 1] != p[i]) 
            j = nxt[j];
        if(p[j + 1] == p[i])
            j++;
        nxt[i] = j;
    }

    j = 0;
    //回退 算f
    for(int i = 1; i <= n; i++) {
        while((j == m) || (j > 0 && p[j + 1] != s[i]))
            j = nxt[j];
        if(p[j + 1] == s[i])
            j++;
        f[i] = j;
    }
    std::cout << m - nxt[m] << endl;
}


void JiuCherish(){
    std::cin >> p + 1;
    kmp();
}
Question 3:[UVA 12467] Secret word

给你一个字符串 s，你需要找出 s 中最长的 secret word，一个字符串 p 是 secret word 需要满足：

  • p 是 s 的子串（p 可以与 s 相等）；
  • 将 p 翻转后是 s 的前缀。

输入一行字符串 s，输出一行字符串为你求得的 p。

题解：就是讲字符串延长2倍，然后跑一个kmp，找到最大的nxt值，最后反向打印即可。

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
int n,m;
int nxt[MAXN],f[MAXN];
char s[MAXN],p[MAXN];
//kmp head

void kmp() {
    //算nxt
    n = strlen(s + 1);
    m = strlen(p + 1);
    p[m + 1] = '#';
    for(int i = m + 2,j = m; j; --j, ++i)
        p[i] = p[j];
    int j = 0;
    nxt[1] = 0;
    for(int i = 2; i <= m + m + 1; i++) {
        while(j > 0 && p[j + 1] != p[i]) 
            j = nxt[j];
        if(p[j + 1] == p[i])
            j++;
        nxt[i] = j;
    }

    j = 0;
    //回退 算f
    for(int i = 1; i <= n; i++) {
        while((j == m) || (j > 0 && p[j + 1] != s[i]))
            j = nxt[j];
        if(p[j + 1] == s[i])
            j++;
        f[i] = j;
    }
    int x = 0;
    for(int i=m+2;i<=m+m+1;i++) {
        x = std::max(x,nxt[i]);
    }
    for(int i = x;i>=1;i--) {
        std::cout << p[i];
    }
}


void JiuCherish(){
    std::cin >> p + 1;
    kmp();
}

扩展KMP（Z algorithm）

与kmp区别：两者求next数组不同，一个是到字符s[i]结束，另一个是从字符s[i]开始。

思路：

代码解读：

对于满足 i > 1 的位置 i , z[i] 表示字符串 s 和后缀 s[i]~s[n] 的最长公共前缀的长度。

如何求 z 数组呢？

首先 z[1] = 0 ，开始往后枚举每个位置，去计算。

若是算第 z[i] 的值，此时 从 1 到 i 的结果一定是算好的。

对于 j, 有 s[j] … s[j + z[j] - 1] 和 s[1] … s[z[j]] 完全相等。

为了计算 z[i] ，在枚举 i 的过程中，我们需要维护一个 R 最大的区间 [L,R]。

其中 L = j (j < i), R = j + z[j] - 1。

情况一：假如 i <= R

我们知道：s[L] 到 S[R] 一定和区间 S[1] 到 S[R - L + 1] 是一一映射的关系。

那么我们约定一个数 k = i - L + 1，那么此时在[L,R]中的位置对应了 k 在 [1,R - L + 1] 中的位置，此时 s[i] 到 S[R] 和 S[k] 到 S[R - L + 1 是一一映射的。

Case1 : 如果 z[k] < R - i + 1，那么匹配不到右边，此时只能z[i] = z[k]

Case2 : 如果 z[k] >= R - i + 1 那么 i 是能匹配到 R 的，这时从 R + 1 开始暴力向后匹配即可。

情况二：假如 i > R

那么暴力枚举匹配即可。

求出 z[i] 后 需要更新 L 和 R。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void exkmp() {
    int L = 1, R = 0;
    z[1] = 0;
    for(int i = 2; i <= n; i++) {
        if(i > R)  z[i] = 0;
        else  {
            int k = i - L + 1;
            z[i] = std::min(z[k],R - i + 1);
        }
        while(i + z[i] <= n && s[z[i] + 1] == s[i + z[i]]) ++z[i];
        if(i + z[i] - 1 > R)
            L = i,R = i + z[i] - 1; 
    }
}

时间复杂度：O(n)

Question 1: exkmp板子题（同上面的kmp板子）

给你两个字符串 a,b，字符串均由小写字母组成，现在问你 b 在 a 中出现了几次。

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 MAXN = 2e5 + 10;
int n,m;
int z[MAXN];
char s[MAXN],p[MAXN];
//exkmp head

void exkmp() {
    n = strlen(s + 1);
    m = strlen(p + 1);
    p[m + 1] = '#';
    for(int i = m + 2, j = 1; j <= n; i++, j++) p[i] = s[j];
    int L = 1, R = 0;
    z[1] = 0;
    for(int i = 2; i <= n + m + 1; i++) {
        if(i > R)  z[i] = 0;
        else  {
            int k = i - L + 1;
            z[i] = std::min(z[k],R - i + 1);
        }
        while(i + z[i] <= n + m + 1 && p[z[i] + 1] == p[i + z[i]]) ++z[i];
        if(i + z[i] - 1 > R)
            L = i,R = i + z[i] - 1; 
    }
    int ans = 0;
    for(int i = m + 1;i <= n + m + 1;i++) {
        if(z[i] == m) ++ans;
    }
    if(!ans) 
        std::cout << -1 << endl << -1 << endl;
    else {
        std::cout << ans << endl;
        for(int i = m + 2;i <= n + m + 1;i++) {
            if(z[i] == m)
                std::cout << i - m - 1 << " ";
        }
        std::cout << endl;
    }
}

void JiuCherish(){
    std::cin >> s + 1 >> p + 1;
    exkmp();
}
Question 2:[CF 126B] Password

给你一个字符串 s，由小写字母组成，你需要求出其中最长的一个子串 p，满足 p 既是 s 的前缀，又是 s 的后缀，且在 s 中以非前缀后缀的形式出现过。如果找不到输出 Just a legend。

输入一行一个字符串 s，输出一行一个字符串 p。

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
const int MAXN = 1e6 + 10;
int n,m;
int z[MAXN];
char s[MAXN];
//exkmp head

void exkmp() {
    n = strlen(s + 1);
    int L = 1, R = 0;
    z[1] = 0;
    for(int i = 2; i <= n; i++) {
        if(i > R)  z[i] = 0;
        else  {
            int k = i - L + 1;
            z[i] = std::min(z[k],R - i + 1);
        }
        while(i + z[i] <= n + m + 1 && s[z[i] + 1] == s[i + z[i]]) ++z[i];
        if(i + z[i] - 1 > R)
            L = i,R = i + z[i] - 1; 
    }
    int ans = 0,x = 0;
    for(int i=1;i<=n;i++) {
        if(i + z[i] - 1 == n) {
            if(x >= z[i]) {
                ans = std::max(ans,z[i]);
            }
        }
        x = std::max(x,z[i]);
    }
    if(!ans) {
        std::cout << "Just a legend" << endl;
    } else {
        for(int i=1;i<=ans;i++) std::cout << s[i];
    }
}

void JiuCherish(){
    std::cin >> s + 1;
    exkmp();
}