题目很绕 ， 其实就是一句话
怎么求 ？？？？？ （白问）
这很明显是一个匹配问题
具体得说 ： 两个串进行匹配
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; }
原文：https://www.cnblogs.com/maowuyou/p/11913888.html