MENU

【中等】KMP字符串

• June 9, 2021 • Read: 292 • 数据结构与算法,学习笔记,算法&题库

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

输入格式

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

输入格式

共一行,输出所有出现位置的起始下标(下标从 $\rm{0}$ 开始计数),整数之间用空格隔开。

数据范围

$\rm{1} \le N \le 10^4$
$\rm{1} \le M \le 10^5$

输入样例

3
aba
5
ababa

输出列表

0 2

题解

(KMP) $O(m+n)$
KMP 算法是 D.E.Knuth、J,H,Morris 和 V.R.Pratt 三位神人共同提出的,称之为 Knuth-Morria-Pratt 算法,简称 KMP 算法。该算法相对于 Brute-Force(暴力)算法有比较大的改进,主要是消除了主串指针的回溯,从而使算法效率有了某种程度的提高。

KMP 算法的关键就是求 next 数组:
next 数组长度与字符串长度一致,每个位置存储对应字符的最长匹配长度。
next 数组即 next[i] = length; 长度为 $i$ 的数组的前缀和后缀相等的最大长度。 例如 $abcdeabc$ 就是 next[8] = 3; 相等的前缀和后缀最长是 $abc$ 长度为 $\rm{3}$。
为了更透彻理解 next 数组,我们来举一个例子
模板串 $P$ 为:$abababab$(令其下标从 $\rm{1}$ 开始)
next[1] 即模板串中取长度为 $\rm{1}$ 的串,如果匹配失败,则退回到起点,故 next[1]=0
next[2] 即模板串中取长度为 $\rm{2}$ 的串,显然其前缀 $a$ 和后缀 $b$ 不相等,故 next[2]=0
next[3] 即模板串中取长度为 $\rm{3}$ 的串,其前缀 $a$ 和后缀 $a$ 相等,$a$ 的长度为 $\rm{1}$,故 next[3]=1

$$ \vdots $$

next[6] 即模板串中取长度为 $\rm{6}$ 的串($ababab$),其前缀 $abab$ 和后缀 $abab$ 相等,该字串长度为 $\rm{4}$ ,故 next[6]=4,以此类推,next[7]=5

到此,我们应该明白 next 数组的意义了,现在我们加上模式串 $S$ 来看,假设 $S$ 为:$abababcab$(同样令其下标从 $\rm{1}$ 开始),以下矩阵代表当前两个字符串的对应关系:

$$ \left[ \begin{array}{l} {\rm{a b a b a b c a b}}\\ {\rm{a b a b a b a b x}} \end{array} \right] $$

($x$ 代表空格),可见在 s[7] 时 $c$ 与 模板串 p[j + 1] 中 $a$ 不匹配,此时,我们如果令 j = next[j],当前 $j=6$ 令 j=next[j]=4 后会发生什么,请看矩阵:

$$ \left[ \begin{array}{l} {\rm{a b a b a b c a b x x x}}\\ {\rm{x x a b a b a b a b x x}} \end{array} \right] $$

为什么要这样操作?
因为我们 next[i] 长度为 $i$ 的数组的前缀和后缀相等的最大长度,刚才我们已经判断得到 p[1] $ \sim$ p[6] 一定是和 s[1] $\sim$ s[6] 完全匹配的,又因为 next[i]=4,故 p[1] $ \sim$ p[6]的前 $\rm{4}$ 个字符与后 $\rm{4}$ 个字符是完全相同的,也就得到 p[1] $ \sim$ p[4] 与 p[3] $ \sim$ p[6]完全相同,则 p[1] $ \sim$ p[4] 也与 s[3] $ \sim$ s[6] 完全相同(因为 p[1] $ \sim$ p[6] 和 s[1] $\sim$ s[6] 完全匹配),所以我们就没必要再从 p[1] 开始枚举,直接从 p[4 + 1]开始即可。

这样操作我们就省去了主串指针的回溯所花费的不必要的时间,接下来的步骤以此类推,详见 C++ 代码部分的 kmp 匹配过程。

C++ 代码

#include <iostream>

using namespace std;

const int N = 10010, M = 100010;

int n, m;
char p[N], s[M];
int ne[N]; //next数组

int main()
{
    cin >> n >> (p + 1) >> m >> (s + 1); //下标从1开始
    //求next数组过程
    for (int i = 2, j = 0; i <= n; i++)//i从2开始即可,i=1不匹配的话即是退为0,不考虑
    {
        while(j && p[i] != p[j + 1])
            j = ne[j];
        if(p[i] == p[j + 1])
            j++;
        ne[i] = j;
    }
    //kmp匹配过程
    for (int i = 1, j = 0; i <= m; i++)
    {
        while (j && s[i] != p[j + 1]) //j未回退到起点,且当前不匹配
            j = ne[j];                //ne[j]表示p[j+1]前端和s匹配的最小移动坐标
        if (s[i] == p[j + 1])
            j++;
        if (j == n)
        {
            printf("%d ", i - n);//起始下标
            j = ne[j];
        }
    }
    return 0;
}

Archives QR Code
QR Code for this page
Tipping QR Code