给定一个模式串 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 数组即 nexti = length; 长度为 i 的数组的前缀和后缀相等的最大长度。 例如 abcdeabc 就是 next8 = 3; 相等的前缀和后缀最长是 abc 长度为 \rm{3} 。为了更透彻理解 next 数组,我们来举一个例子:模板串 P 为:abababab (令其下标从 \rm{1} 开始)
为什么要这样操作?因为我们 nexti 长度为 i 的数组的前缀和后缀相等的最大长度,刚才我们已经判断得到 p1 \sim p6 一定是和 s1 \sim s6 完全匹配的,又因为 nexti=4,故 p1 \sim p6的前 \rm{4} 个字符与后 \rm{4} 个字符是完全相同的,也就得到 p1 \sim p4 与 p3 \sim p6完全相同,则 p1 \sim p4 也与 s3 \sim s6 完全相同(因为 p1 \sim p6 和 s1 \sim s6 完全匹配),所以我们就没必要再从 p1 开始枚举,直接从 p4 + 1开始即可。
这样操作我们就省去了主串指针的回溯所花费的不必要的时间,接下来的步骤以此类推,详见 C++ 代码部分的 kmp 匹配过程。
#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;
}