记录编号	95277	评测结果	AAAAAAAAAA
题目名称	[USACO Dec05]可疑的斑点	最终得分	100
用户昵称	Chenyao2333	是否通过	通过
代码语言	C++	运行时间	0.086 s
提交时间	2014-04-04 22:22:42	内存使用	2.60 MiB

#include<stdio.h>
#include<iostream>


using namespace std;
const int MAXN=100000+10;

typedef unsigned long long ULL;
const ULL X=204801569;

int N,K,S,MN;
int s_n[MAXN];
int k_s[MAXN];

ULL x_z[MAXN];
void cal_x_z(){
	x_z[0]=1;
	for(int i=1;i<MN;i++){
		x_z[i]=x_z[i-1]*X;
	}
}

inline ULL add_num(ULL h,ULL del,ULL add,int size){
	h-=del*x_z[size];
	h*=X;
	h+=add*X;
	return h;
}

void read(){
	scanf("%d %d %d",&N,&K,&S);MN=K+10;
	for(int i=1;i<=N;i++)scanf("%d",&s_n[i]);
	for(int i=1;i<=K;i++)scanf("%d",&k_s[i]);
}

int ans_n[MAXN];

ULL cal_hash(int *arr,int a,int b){
	ULL ans=0;
	for(int i=a;i<=b;i++){
		ans=add_num(ans,0,arr[i],i-a-1);
	}
	return ans;
}

int s_num[30]={0};
int s_rank[30]={0};
int rank[MAXN]={0};

void cal_s_rank(){
	int r=1;
	for(int i=1;i<=S;i++){
		if(s_num[i])s_rank[i]=r++;
	}
}

void cal_rank(int a,int b){
	for(int i=a;i<=b;i++){
		rank[i]=s_rank[s_n[i]];
	}
}

void work(){
	read();
	cal_x_z();
	int ans=0;
	ULL Ha=cal_hash(k_s,1,K);
	ULL Hb=0;
	for(int i=1;i<=K;i++){
		int s=s_n[i];
		s_num[s]++;
	}
	cal_s_rank();
	cal_rank(1,K);
	Hb=cal_hash(rank,1,K);
	if(Ha==Hb){
		ans_n[ans++]=1;
	}
	for(int i=1;i+K<=N;i++){
		int x=s_n[i];
		int y=s_n[i+K];
		rank[i+K]=s_rank[y];
		s_num[x]--;s_num[y]++;
		//rank[x]--;rank[y]++;
		if(s_num[x]==0 || s_num[y]==1 || !y){
			cal_s_rank();
			y=s_rank[s_n[i+K]];
			rank[i+K]=y;
			cal_rank(i+1,i+K);		
			Hb=cal_hash(rank,i+1,i+K);
		}else{
			Hb=add_num(Hb,s_rank[x],s_rank[y],K);
		}
		if(Ha==Hb){
			ans_n[ans++]=i+1;
		}
	}
	cout<<ans<<endl;
	for(int i=0;i<ans;i++){
		printf("%d\n",ans_n[i]);
	}
}

void open(){
	//freopen("in.txt","r",stdin);
	freopen("cpattern.in","r",stdin);
	freopen("cpattern.out","w",stdout);
}

int main(){
	open();
	work();
}