KMP算法是一个著名的字符串匹配算法,效率很高,但是确实有点复杂。
KMP 算法是 D.E.Knuth、J,H,Morris 和 V.R.Pratt 三位神人共同提出的,称之为 Knuth-Morria-Pratt 算法,简称 KMP 算法。该算法相对于 Brute-Force(暴力)算法有比较大的改进,主要是消除了主串指针的回溯,从而使算法效率有了某种程度的提高。
上面说道 KMP 算法主要是通过消除主串指针的回溯来提高匹配的效率的,那么,它是则呢样来消除回溯的呢?就是因为它提取并运用了加速匹配的信息!
这种信息就是对于每模式串 t 的每个元素 t j,都存在一个实数 k ,使得模式串 t 开头的 k 个字符(t 0 t 1…t k-1)依次与 t j 前面的 k(t j-k t j-k+1…t j-1,这里第一个字符 t j-k 最多从 t 1 开始,所以 k < j)个字符相同。如果这样的 k 有多个,则取最大的一个。模式串 t 中每个位置 j 的字符都有这种信息,采用 next 数组表示,即 next[ j ]=MAX{ k }。
这里并没有将next数组,如果您想看,我推荐这位大佬的博文:点这里
// s[]是长文本,p[]是模式串,n是s的长度,m是p的长度
//求模式串的Next数组:
for (int i = 2, j = 0; i <= m; i++) {
while (j && p[i] != p[j + 1])
j = ne[j];
if (p[i] == p[j + 1])
j++;
ne[i] = j;
}
// 匹配
for (int i = 1, j = 0; i <= n; i++) {
while (j && s[i] != p[j + 1])
j = ne[j];
if (s[i] == p[j + 1])
j++;
if (j == m) {
j = ne[j];
// 匹配成功后的逻辑
}
}
给定一个字符串 S,以及一个模式串 P,所有字符串中只包含大小写英文字母以及阿拉伯数字。模式串 P在字符串 S
中多次作为子串出现。求出模式串 P在字符串 S中所有出现的位置的起始下标。
输入格式
第一行输入整数 N,表示字符串 P的长度。
第二行输入字符串 P。
第三行输入整数 M,表示字符串 S的长度。
第四行输入字符串 S。
输出格式
共一行,输出所有出现位置的起始下标(下标从 0
开始计数),整数之间用空格隔开。
数据范围
1≤N≤105
1≤M≤106
输入样例:
3
aba
5
ababa
输出样例:
0 2
#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 1000010;
int n, m;
int ne[N];
char s[M], p[N];
int main() {
cin >> n >> p + 1 >> m >> s + 1;
for (int i = 2, j = 0; i <= n; i++) {
while (j && p[i] != p[j + 1])
j = ne[j];
if (p[i] == p[j + 1])
j++;
ne[i] = j;
}
for (int i = 1, j = 0; i <= m; i++) {
while (j && s[i] != p[j + 1])
j = ne[j];
if (s[i] == p[j + 1])
j++;
if (j == n) {
printf("%d ", i - n);
j = ne[j];
}
}
return 0;
}
注:csdn的不怕困难的博客即将搬家至本博客,敬请期待!
手机扫一扫
移动阅读更方便
你可能感兴趣的文章