自动搬运

查看原文

来自洛谷，原作者为

	maowuyou **

搬运于2025-08-24 22:02:42，当前版本为作者最后更新于2019-08-19 14:29:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

KMP + 重新定义相等

题目传送器

题目很绕 ， 其实就是一句话

给你两个排列 P 、H， 求 H 中 任意一段 连续的 排列 与P相同的序列

怎么求 ？？？？？ （白问）

这很明显是一个匹配问题

具体得说 ： 两个串进行匹配

KMP 就是 在线性时间 完成这种题目 的 算法

考虑怎么 KMP ？

很容易想到 ， 匹配数字串 和 匹配 字符串的大致思路没有差别

匹配 单纯的数字串 和 匹配 “排列串” 的差别 仅仅在只是在 判断相等 上有差别

所以 匹配 “排列串” 和 比配 字符串的差别 在于 判断相等

现在所有人应该都能理解标题中的 “重新定义相等” 了 吧

现在难点变为 ： 如何重新定义 “相等”

以前看到过一句话 ： 你定义两个事物的某个特性一样时，称两个事物相等

那么 你定义的标准 肯定是你 最看重的

P 是 一个排列

何为排列 ？ 排序后的列的顺序

顺序与什么有关 ？ “比他大的数的个数” 和 “比他小的数的个数 ”

所以相等就被定义为 在一个范围内 h[i] 与和其匹配的c[i] 有 一样多的 “比他大的数的个数” 和 “比他小的数的个数 ”

于是乎 离散化 + 树状数组 的解法 就出现了

但对于我这种蒟蒻而言 ， 数据结构太难了！！！

所以我们换一种角度

其实很容易就能想到

c[i] 若满足 p[i] 的排列（即 c[i] 在这一段范围内排在与 p[i] 同样的位置）

也是能算作匹配的

于是我们预处理处 P 排列中 p[i] 的 前驱和后继 的位置

匹配时 ，判断 c[i] 是否 大于（或小于） 他所要匹配的 p[i] 的 前驱 （或后继）

这样的匹配是 O(1) 的

似乎比 树状数组还快

就形成了这个玄学算法

请各位仔细感性理解

代码如下

#include<bits/stdc++.h>
#define MAXN 1000005
int a[MAXN],b[MAXN],c[MAXN],p[MAXN];
int pre[MAXN],net[MAXN],L[MAXN],R[MAXN];
int ans[MAXN];
int n,m,k;
bool check(int P[],int u,int v)
{
	return P[v+L[u]]<=P[v] && P[v+R[u]]>=P[v];
}
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&b[i]);
		a[b[i]]=i;
		pre[i]=i-1;
		net[i]=i+1;
	}
	for(int i=n;i>=1;i--)
	{
		int j=a[i];
		if (pre[j]) L[i]=b[pre[j]]-i;
		if (net[j]<=n) R[i]=b[net[j]]-i;
		pre[net[j]]=pre[j];
		net[pre[j]]=net[j];
	}
	for(int i=2,j=0;i<=n;i++)
	{
		while (j && !check(a,j+1,i)) j=p[j];
		if (check(a,j+1,i)) j++;
		p[i]=j;
	}
	for(int i=1;i<=m;i++) scanf("%d",&c[i]);
	for(int i=1,j=0;i<=m;i++)
	{
		while (j && !check(c,j+1,i)) j=p[j];
		if (check(c,j+1,i)) j++;
		if (j==n)
		{
			ans[++k]=i-n+1;
			j=p[j];
		} 
	}
	printf("%d\n",k);
	if (k==0)
	{
		puts("");
		return 0;
	}
	for(int i=1;i<=k;i++) printf("%d ",ans[i]);
	return 0;
}

希望这道题能让你更好理解KMP

理解 事物间的相等关系

理解匹配的真谛