这道题确实让我更加深入的了解了kmp。。。。
以前的匹配只要字符或者是数值一样就可以，这道题是区间名次一样进行匹配的。
一个数在区间中的名次可以转化为，它前面比他小的数的个数，和他相等的个数，和比他大的个数。
一个数显然不行，但是如果一个区间内所有数的这三个值都对应相等，那么这两个区间就是等价的。
可以用线段树来维护区间。
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
using namespace std;
int cow[100100],pa[25010];
int p1[25100],p2[25100];//p1小于，p2等于
int tree[100100];int cnt;
#define lson 2*o,l,mid
#define rson 2*o+1,mid+1,r
void insert(int o,int l,int r,int a,int x)
{
if(l>r||a>r||a<l)return;
if(l==r&&l==a)
{
tree[o]+=x;
return;
}
int mid=(l+r)>>1;
insert(lson,a,x);
insert(rson,a,x);
tree[o]=tree[2*o]+tree[2*o+1];
}
int query(int o,int l,int r,int a,int b)
{
if(a>b)return 0;
if(a>r||b<l)return 0;
if(a<=l&&r<=b)
{
return tree[o];
}
int mid=(l+r)>>1;
return query(lson,a,b)+query(rson,a,b);
}
void init(int n,int s,int k)
{
int x;cnt=0;
memset(tree,0,sizeof(tree));
memset(p1,0,sizeof(p1));
memset(p2,0,sizeof(p2));
memset(pa,0,sizeof(pa));
memset(cow,0,sizeof(cow));
for(int i=1;i<=n;i++)
{
scanf("%d",&cow[i]);
}
memset(tree,0,sizeof(tree));
for(int i=1;i<=k;i++){
scanf("%d",&x);
pa[i]=x;
insert(1,1,s,x,1);
p1[i]=query(1,1,s,1,x-1);
p2[i]=query(1,1,s,x,x);
}
}
int nex[25100];
int ans[100100];
void getnext(int n,int s)
{
int k=0,j=1;
int sum1,sum2;
nex[0]=0;
memset(tree,0,sizeof(tree));
while(j<=n){
sum1=query(1,1,s,1,pa[j]-1);
sum2=query(1,1,s,pa[j],pa[j]);
if(k==0||(sum1==p1[k]&&sum2==p2[k]))
{
j++;k++; nex[j]=k;
if(j==n+1)return;
insert(1,1,s,pa[j],1);
}
else{
int end=j-nex[k]+1;
for(int i=j-k+1;i<end;i++){
insert(1,1,s,pa[i],-1);
}
k=nex[k];
}
}
}
void kmp(int n,int k,int s)
{
memset(tree,0,sizeof(tree));
int i=1,j=1;
int sum1,sum2;
insert(1,1,s,cow[1],1);
while(i<=n)
{
sum1=query(1,1,s,1,cow[i]-1);
sum2=query(1,1,s,cow[i],cow[i]);
if(j==0||((sum1==p1[j]&&sum2==p2[j]))){
i++;j++;
if(i<=n)insert(1,1,s,cow[i],1);
}
else{
int end=i-nex[j]+1;
for(int x=i-j+1;x<end;x++){
insert(1,1,s,cow[x],-1);
}
j=nex[j];
}
if(j>k){
ans[cnt++]=i-k;
int end=i-nex[j]+1;
for(int x=i-j+1;x<end;x++){
insert(1,1,s,cow[x],-1);
}
j=nex[j];
}
}
}
int main()
{
int n,k,s;
scanf("%d%d%d",&n,&k,&s);
init(n,s,k);
getnext(k,s);
kmp(n,k,s);
printf("%d\n",cnt);
for(int i=0;i<cnt;i++){
printf("%d\n",ans[i]);
}
//system("pause");
return 0;
}