本文共 2001 字，大约阅读时间需要 6 分钟。

$$\mathrm{KMP字符串匹配}$$

题目链接：

题目

给出两个字符串 $s_1$ 和 $s_2$ ，若 $s_1$ 的区间 $[l,r]$ 子串与 $s_2$ 完全相同，则称 $s_2$ 在 $s_1$ 中出现了，其出现位置为 $l$ 。

现在请你求出 $s_2$ 在 $s_1$ 中所有出现的位置。

定义一个字符串 $s$ 的 border 为 $s$ 的一个非 $s$ 本身的子串 $t$ ，满足 $t$ 既是 $s$ 的前缀，又是 $s$ 的后缀。

对于 $s_2$ ，你还需要求出对于其每个前缀 $s^{\prime }$ 的最长 border $t^{\prime }$ 的长度。

输入

第一行为一个字符串，即为 $s_1$ 。

第二行为一个字符串，即为 $s_2$ 。

输出

首先输出若干行，每行一个整数，按从小到大的顺序输出 $s_2$ 在 $s_1$ 中出现的位置。

最后一行输出 $|s_2|$ 个整数，第 $i$ 个整数表示 $s_2$ 的长度为 $i$ 的前缀的最长 border 长度。

样例输入

ABABABCABA

样例输出

130 0 1

样例解释

对于 $s_2$ 长度为 $3$ 的前缀 ABA，字符串 A 既是其后缀也是其前缀，且是最长的，因此最长 border 长度为 $1$ 。

数据范围

Subtask $1$ （ $30$ points）： $|s_1|\le 15$ ， $|s_2|\le 5$ 。

Subtask $2$ （ $40$ points）：$|s_1|\le 10^4$ ， $|s_2|\le 10^2$ 。 Subtask $3$ （ $30$ points）：无特殊约定。 对于全部的测试点，保证 $1\le |s_1|,|s_2|\le 10^6$ ， $s_1,s_2$ 中均只含大写英文字母。

思路

这道题是一道模板题。

这个KMP的主要思想就是记住你之前匹配时错误的经验。

我们先让 $s_2$ 和 $s_2$ 匹配，得出一个数组 $p[j]$ ，代表的是当匹配到 $s_2$ 数组的第 $j$ 个字母而第 $j+1$ 个字母不能匹配了时，新的 $j$ 最大是多少。 然后就让两个字符串匹配，找到能匹配的，输出出来。

最后要输出 border ，其实就是我们的 $p[j]$ 。

那其实就没了。

代码

#include
   
    #include
    
     using namespace std;int asize, bsize, j, p[1000001];char a[1000001], b[1000001];int main() {   	scanf("%s %s", a + 1, b + 1);//读入	asize = strlen(a + 1);//求出两个字符串的长度	bsize = strlen(b + 1);		j = 0;	for (int i = 2; i <= bsize; i++) {   //s2和s2匹配		while (j && b[i] != b[j + 1]) j = p[j];//匹配不了		if (b[i] == b[j + 1]) j++;//这一个匹配成功		p[i] = j;	}		j = 0;	for (int i = 1; i <= asize; i++) {   //s1和s2匹配		while (j && a[i] != b[j + 1]) j = p[j];		if (a[i] == b[j + 1]) j++;		if (j == bsize) {   			printf("%d\n", i - bsize + 1);//匹配的出来			j = p[j];		}	}		for (int i = 1; i <= bsize; i++)		printf("%d ", p[i]);//输出		return 0;}
    
   

转载地址：http://vhph.baihongyu.com/