题解 P4696 【[CEOI2011]Matching】

# KMP + 重新定义相等 [题目传送器](https://www.luogu.org/problem/P4696) 题目很绕 ， 其实就是一句话 #### 给你两个排列 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) 的 ~~似乎比 树状数组还快~~ 就形成了这个玄学算法 请各位仔细感性理解 代码如下 ```cpp #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 理解 事物间的相等关系 理解匹配的真谛