字符串模式匹配之KMP算法＜- AcWing

【问题描述】
给定一个主串S，以及一个模式串T。且所有字符串中只包含大小写英文字母以及阿拉伯数字。
模式串T在主串S中多次作为子串出现。
求出模式串T在主串S中所有出现的位置的开始下标。

【输入格式】
第一行输入整数M，表示模式串T的长度。
第二行输入模式串T。
第三行输入整数 N，表示主串S的长度。
第四行输入主串S。

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

【数据范围】
1≤N≤10^5
1≤M≤10^6

【输入样例】
3
aba
5
ababa

【输出样例】
0 2

【算法分析】
KMP算法本身并不复杂，主要分为两步：求next[ ]数组、匹配字符串。但绝大部分的文章把它讲混乱了，以致造成很多混淆。
KMP算法每次在失配时，不是把模式串T往后移动一位，而是把模式串T往后移动至下一次可以和前面部分匹配的位置，这样就可以跳过大多数的失配步骤。而每次模式串T移动的步数就是通过查找next[ ]数组确定的。next[ ]数组，是KMP算法的核心。
偶尔发现 https://www.acwing.com/solution/content/14666/ 文章讲得太好了，现加上个人见解分享之。

一、next[ ]数组的含义
next[ ]数组，既然是KMP算法的核心，因此在编码实现前就十分有必要了解一下求解next[ ]数组的思想以及涉及的基本概念。
1.求解next[ ]数组涉及到的基本概念
“非平凡前缀”：指除了最后一个字符以外，一个字符串的全部头部组合。简称前缀。
“非平凡后缀”：指除了第一个字符以外，一个字符串的全部尾部组合。简称后缀。
“部分匹配值”：前缀和后缀集合中最长共有元素的长度。
“部分匹配值表”，即next[ ]数组。它存储的是每一个下标对应的“部分匹配值”，是KMP算法的核心。
2.求解next[ ]数组的基本思想
下图是通过前缀和后缀集合中最长共有元素的长度，来构建“部分匹配值表”，即next[ ]数组的过程。

二、求next[ ]数组的代码
next[ ]数组的求法，是通过模式串T自己与自己进行匹配得出来的（代码和下文“匹配字符串”的操作几乎一样）。

for(int i=2, j=0; i<=m; i++) { //求next[]数组。i从2开始，j从0开始。
	while(j && t[i]!=t[j+1]) j=ne[j]; //由于移动后可能仍然失配，所以要用while继续移动
	if(t[i]==t[j+1]) j++;
	ne[i]=j;
}

下图是T[a,b]=T[1,j]时，模式串T的状态。

若执行语句 if(t[i]==t[j+1]) j++; 后，将产生下图的状态，再结合next[ ]数组的定义，分析可得 next[i]=j;若注意到下图中，绿色虚线框内的元素是相同的，再结合next[ ]数组的定义就更好理解所得结论了。

三、匹配字符串的代码
next[ ]数组在某字符处对应的值的大小，即图中黄色花括号表示的大小。

for(int i=1, j=0; i<=n; i++) { //匹配操作。i从1开始，j从0开始
	while(j && s[i]!=t[j+1]) j=ne[j];
	if(s[i]==t[j+1]) j++;
	if(j==m) {
		cout<<i-m<<" ";
		j=ne[j]; //再次继续匹配
	}
}

【算法代码】

#include <bits/stdc++.h>
using namespace std;

const int maxs=1000010; //maxs为主串最大长度
const int maxt=100010; //maxt为模式串最大长度

char s[maxs]; //s为主串
char t[maxt]; //t为模式串
int ne[maxt]; //next[]数组
int m,n;

int main() {
	cin>>m>>t+1>>n>>s+1; //s[]及t[]数组下标从1开始

	for(int i=2, j=0; i<=m; i++) { //求next[]数组。i从2开始，j从0开始。
		while(j && t[i]!=t[j+1]) j=ne[j]; //由于移动后可能仍然失配，所以要用while继续移动
		if(t[i]==t[j+1]) j++;
		ne[i]=j;
	}

	for(int i=1, j=0; i<=n; i++) { //匹配操作。i从1开始，j从0开始
		while(j && s[i]!=t[j+1]) j=ne[j];
		if(s[i]==t[j+1]) j++;
		if(j==m) {
			cout<<i-m<<" ";
			j=ne[j]; //再次继续匹配
		}
	}

	return 0;
}


/*
in:
3
aba
5
ababa

out:
0 2
*/

【参考文献】
http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/
https://www.acwing.com/solution/content/14666/
https://blog.csdn.net/Kerryliuyue/article/details/108186388
https://blog.csdn.net/hnjzsyjyj/article/details/109489506