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

题目描述

给出两个字符串 $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 长度。

输入输出样例

输入 #1

ABABABCABA

输出 #1

130 0 1

说明/提示

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

数据规模与约定

本题采用多测试点捆绑测试，共有 $3$ 个子任务。

• 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算法的稍微变形，要输出文本串中所有和模式串匹配的位置，以及 next 数组。

---

思路：KMP完成一次匹配的时间复杂度是 $\text{O(m+n)}$ ，即使像 HDU 2087 剪花布条 那样不重叠地匹配文本串中的多个模式串，时间复杂度也是 $\text{O(m+n)}$。但是本题如果不想一下，就可能被卡到 $\text{O(mn)}$ 的复杂度。

下面的代码按照样例解释进行，在用 nextArr 数组完成一次模式串的匹配后，会像暴力匹配算法一样，将 i 回溯到原来的下个位置，j = 0 。于是，会有两个点 TLE ：

#include 
   
    using namespace std;const int MAXN = 1e6 + 10;char s[MAXN], p[MAXN];int nextArr[MAXN], slen, plen; namespace kmp1 {
   	void getNext() {
   		nextArr[0] = 0, nextArr[1] = 0;		for (int i = 1; i < plen; ++i) {
   			int j = nextArr[i];			while (j && p[i] != p[j]) j = nextArr[j];			nextArr[i + 1] = (p[i] == p[j] ? j + 1 : 0);		}	}	void kmp() {
   		slen = strlen(s), plen = strlen(p);		getNext();		if (slen < plen) return;		int j = 0;		for (int i = 0; i < slen; ++i) {
   			while (j && s[i] != p[j]) j = nextArr[j];			if (s[i] == p[j]) ++j;			if (j >= plen) {
   	//如果匹配完成一次 				printf("%d\n", i + 1 - j + 1);				i = i - j + 1;				j = 0;			}		}	}} namespace kmp2 {
   	void getNext() {
     		nextArr[0] = -1, nextArr[1] = 0;		int pos = 2, cn = 0;		while (pos <= plen) {
   			if (p[pos - 1] == p[cn]) nextArr[pos++] = ++cn;				else if (cn > 0) cn = nextArr[cn];			else nextArr[pos++] = cn;		}	}	void kmp() {
   		slen = strlen(s), plen = strlen(p);		getNext();		if (slen < plen) return; 		int i = 0, j = 0;  		while (i < slen && j < plen) {
   			if (s[i] == p[j]) ++i, ++j;			else if (nextArr[j] != -1) j = nextArr[j]; //j != 0			else ++i;								   //j = 0失配 //	        else if (nextArr[j] == -1) ++i;//	        else j = nextArr[j];			if (j >= plen) {
    //如果匹配完成一次				printf("%d\n", i - j + 1);				i = i - j + 1;				j = 0;			}		}	}}void printNextArr() {
   	for (int i = 1; i <= plen; ++i)		printf("%d ", nextArr[i]);		printf("\n");}int main() {
   	scanf("%s %s", s, p);	kmp1::kmp();	//kmp2::kmp();	printNextArr();    return 0;}
   

只用改几句就可以过了，我们将模式串的匹配完成视作 j = p[plen] = '\0' ，此时一定会和 i 失配，于是 j = next[j] ，而 i 不进行回溯：

...	if (j >= plen) {
   		printf("%d\n", i - j + 1);		j = nextArr[j];	}	...

提交，可以通过：

转载地址：https://memcpy0.blog.csdn.net/article/details/108239684 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！