解法:这题就是kmp匹配过程中用树状数组维护每个数字出现的次数,快速查询在前面比自己小的和等于自己的来判断是否能向后匹配

///BZOJ 1461
///KMP + BIT

#include <bits/stdc++.h>
using namespace std;
const int maxn = 500010;
const int maxs = 10010;
int n, k, s;
int a[maxn], b[maxn], fail[maxn];
int rnk1[maxn], rnk2[maxn];
vector <int> ans;
int c[maxn];
inline int lowbit(int x){return x&-x;}
inline void add(int x, int v){for(int i=x; i<=s; i+=lowbit(i)) c[i]+=v;}
inline int query(int x){
    if(x==0) return 0;
    int ret = 0;
    for(int i=x; i; i-=lowbit(i)) ret += c[i];
    return ret;
}
inline void kmp(){

}

int main(){
    scanf("%d%d%d", &n,&k,&s);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    for(int i=1; i<=k; i++) scanf("%d", &b[i]), add(b[i], 1), rnk1[i]=query(b[i]), rnk2[i]=query(b[i]-1);
    int i, j, m;
    fail[1]=j=0;
    memset(c, 0, sizeof(c));
    for(int i=2; i<=k; i++){
        add(b[i], 1);
        while(j&&(query(b[i])!=rnk1[j+1]||query(b[i]-1)!=rnk2[j+1])){
            for(m=i-j; m<i-fail[j]; m++) add(b[m],-1);
            j=fail[j];
        }
        fail[i] =j+=(query(b[i])==rnk1[j+1]) && (query(b[i]-1)==rnk2[j+1]);
    }
    j = 0;
    memset(c, 0, sizeof(c));
    for(int i=1; i<=n; i++){
        add(a[i], 1);
        while(j&&(query(a[i])!=rnk1[j+1]||query(a[i]-1)!=rnk2[j+1])){
            for(m=i-j; m<i-fail[j]; m++) add(a[m],-1);
            j=fail[j];
        }
        if(j==k-1){
            ans.push_back(i-j);
            for(m=i-j; m<i-fail[j]; m++) add(a[m],-1);
            j=fail[j];
        }
        ++j;
    }
    int tot = ans.size();
    printf("%d\n", tot);
    for(int i=0; i<tot; i++){
        printf("%d\n", ans[i]);
    }
    return 0;
}