解法：这题就是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; }