两个串相等定义为串中每一位排序后的相对大小相等。
一位相等等价于这一位前面比他小的和等于他的数的个数相等。
那么用kmp，比较的时候比较这两个个数就可以了。
一开始很瓜地想，询问一段区间内比我小和和我相等的数，得写个主席树啊。。。
实际上用个树状数组维护，kmp跑nxt的时候把跳过的部分从树状数组中删除就好了。
//Achen
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rep(i,a,b) for(int i=(a);i>=(b);i--)
const int N=100007;
typedef long long LL;
using namespace std;
int n,k,S,s[N],a[N],nxt[N],l1[N],l2[N],ans[N];
template<typename T> void read(T &x) {
T f=1; x=0; char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') f=-1,ch=getchar();
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
}
int sum[30];
void add(int x,int v) {
if(!x) return;
for(int i=x;i<=25;i+=(i&(-i)))
sum[i]+=v;
}
int qry(int x) {
int rs=0;
for(int i=x;i;i-=(i&(-i)))
rs+=sum[i];
return rs;
}
void make_nxt(int n) {
memset(sum,0,sizeof(sum));
For(i,0,n-1) {
l1[i]=qry(a[i]-1);
l2[i]=qry(a[i]);
add(a[i],1);
}
memset(sum,0,sizeof(sum));
for(int i=1,k=0;i<n;i++) {
while(k&&((qry(a[i]-1)!=l1[k])||(qry(a[i])!=l2[k]))) {
For(j,i-k,i-nxt[k-1]-1) add(a[j],-1);
k=nxt[k-1];
}
if((qry(a[i]-1)==l1[k])||(qry(a[i])==l2[k])) k++;
nxt[i]=k;
add(a[i],1);
}
}
void solve(int n,int m) {
int k=0; ans[0]=0;
memset(sum,0,sizeof(sum));
For(i,0,n-1) {
while(k&&((qry(s[i]-1)!=l1[k])||(qry(s[i])!=l2[k]))) {
For(j,i-k,i-nxt[k-1]-1) add(s[j],-1);
k=nxt[k-1];
}
if((qry(s[i]-1)==l1[k])||(qry(s[i])==l2[k])) k++;
if(k==m) {
ans[++ans[0]]=i-m+1;
For(j,i-k+1,i-nxt[k-1]) add(s[j],-1);
k=nxt[k-1];
}
add(s[i],1);
}
For(i,0,ans[0]) printf("%d
",i==0?ans[i]:ans[i]+1);
}
int main() {
#ifdef DEBUG
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
while(scanf("%d %d %d",&n,&k,&S)==3) {
For(i,0,n-1) read(s[i]);
For(i,0,k-1) read(a[i]);
make_nxt(k);
solve(n,k);
}
return 0;
}
/*
10 3 10
7
8
4
9
6
4
5
10
4
8
10
9
3
*/