KMP 算法

\(Question：\)

给定一个模式串P和一个主串S, 求模式串P在主串S中出现的位置(字符串下标均从1开始)

\(Solution：\)

模式串中

• next 函数

next[i] 表示模式串 P[1, i]中相等前后缀的最长长度

• 运用双指针：i 扫描模式串， j 扫描前缀

• 初始化 ne[1] = 0, i = 2, j = 0;

ne[1] = 0;
for(int i = 2, j = 0; i <= n; i ++) {
    while(j && p[i] != p[i + 1]) j = ne[j]; // 若不等则跳回能匹配的位置
    if(p[i] == p[i + 1]) j ++; // 若匹配则则j + 1，指向匹配前缀的末尾
    ne[i] = j; // next[i] 等于j的值
}

模式串与主串匹配

• 还是运用双指针：i 扫描主串, j 扫描模式串

• 初始化 i = 1, j = 0;

for(int i = 1, j = 0; i <= m; i ++) {
    while(j && s[i] != p[i + 1]) j = ne[j]; // 若不等，让j回跳到能匹配的位置
    if(s[i] == p[i + 1]) j ++; // 若匹配j向右走一步
    if(j == n) cout << i - n + 1 << endl; // 若完全匹配则输出结果
}

总代码

#include <bits/stdc++.h>

using namespace std;

string s, p;
int ne[10005], n, m;

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

注意代码中的字符串下标都是从1开始的，而不是0开始。

• 例题：

P3375 【模板】KMP

#include <bits/stdc++.h>

using namespace std;
const int N = 1e6 + 10;

string s1, s2;
int ne[N];


int main() {
	cin >> s1 >> s2;
	s1 = ' ' + s1, s2 = ' ' + s2;
	ne[1] = 0;
	for(int i = 2, j = 0; i <= s2.size() - 1; i ++) {
		while(j && s2[i] != s2[j + 1]) j = ne[j];
		if(s2[i] == s2[j + 1]) j ++;
		ne[i] = j;
	}
	for(int i = 1, j = 0; i <= s1.size() - 1; i ++) {
		while(j && s1[i] != s2[j + 1]) j = ne[j];
		if(s1[i] == s2[j + 1]) j ++;
		if(j == s2.size() - 1) {
			cout << i - s2.size() + 2 << endl;
			j = ne[j];
		}
	}
	for(int i = 1; i <= s2.size() - 1; i ++) {
		cout << ne[i] << " ";
	}
	return 0;
}