KMP字符串

发表于 更新于 分类于 ，
本文字数： 1.4k

KMP字符串问题的思想

给定一个模式串S，以及一个模板串P，所有字符串中只包含大小写英文字母以及阿拉伯数字，模板串P在模式串S中多次作为子串出现，求出模板串P在模式串S中所有出现的位置的起始下标。

输入格式

第一行输入整数N，表示字符串P的长度。 第二行输入字符串P。 第三行输入整数M，表示字符串S的长度。 第四行输入字符串S。

输出格式

共一行，输出所有出现位置的起始下标（下标从0开始计数），整数之间用空格隔开。

代码实现：

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
#include <iostream>

using namespace std;

const int N = 1e4 + 10, M = 1e5 + 10;

char p[N], s[M];
int ne[N]; 

int main()
{
    int n, m;
    cin >> n >> p + 1 >> m >> s + 1;
    for (int i = 2, j = 0; i <= n; i++)
    {
        while (j && p[j + 1] != p[i])
            j = ne[j];
        if (p[j + 1] == p[i])
            j++;
        ne[i] = j;
    }
    for (int i = 1, j = 0; i <= m; i++)
    {
        while (j && p[j + 1] != s[i])
            j = ne[j];
        if (p[j + 1] == s[i])
            j++;
        if (j == n)
        {
            j = ne[j];
            printf("%d ", i - n);
        }
    }
    return 0;
}

思想：

我们可以从暴力入手

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
#include <iostream>

using namespace std;

const int N = 1e4 + 10, M = 1e5 + 10;

char p[N], s[M];
int ne[N];

int main()
{
    int n, m;
    cin >> n >> p + 1 >> m >> s + 1;
    for (int i = 1; i <= m; i++)
    {
        bool flag = true;
        for (int j = 1; j <= n; j++)
        {
            if (s[i + j - 1] != p[j])
            {
                flag = false;
                break;
            }
        }
        if (flag)
            cout << i - 1 << " ";
    }
    return 0;
}

可以发现，在进行比较时，上一次比较时的信息可以用来优化这次模板串的移动 即转换成模板串最少往后移动多少位的问题 需要预处理模板串，计算出模板串每一位作为后缀子串的终点，与该后缀子串相等的前缀子串最大长度为多少 我们可以创建一个next数组来储存（关键） ne[i]表示以i点为后缀子串终点，相等的前缀子串的最大长度 next数组的创建 和 模式串与模板串的比较过程 的具体实现方法为双指针算法（举例体会）

注：

  • 在两串比较成功一次后，需要一个 j = ne[j]; 的操作，是为了在比对模式串的下一位时模板串移动最少的位数
  • 在创建next数组时 i 从2开始，ne[1] = 0