记录编号	94197	评测结果	AAAAAAAAAA
题目名称	[USACO Dec05]可疑的斑点	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.470 s
提交时间	2014-03-30 21:18:47	内存使用	1.65 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<iomanip>
using namespace std;
const int SIZEN=100010,SIZEK=25010,SIZES=30,INF=0x7fffffff/2;
int N,K,S;
int pattern[SIZEN]={0},ranklis[SIZEK]={0};
int R=0,first[SIZES]={0};
int realnum[SIZEN]={0};//这个初值0和后面的INF是特意设计的
int next[SIZEK]={0};
void getnext(int s[SIZEK],int n,int next[SIZEK],int type){//我们在此只关注type的匹配,即设type之外的统统是零
	next[0]=-1;
	int i=0,j=-1;
	while(i<n){
		while(j!=-1&&(s[i]==type||s[j]==type)&&s[i]!=s[j]) j=next[j];
		next[++i]=++j;
	}
}
bool check(int i,int j,int from,int type,int rank){//是否继续滑动?其中i对type斑点数,j对rank排名
	if(j==K) return true;//不同于平常的KMP,在这里j走到头的时候可能并不会由于失配走fail指针
	if(j==-1) return false;
	if(type<=realnum[from]) return true;//和前面的排名冲突或者匹配不上
	if(ranklis[j]==rank&&pattern[i]!=type) return true;//这个type失配了
	if(ranklis[j]!=rank&&pattern[i]==type) return true;
	return false;
}
int nownum[SIZEN]={0};
void KMP(int type,int rank){
	int i=0,j=0,from=0;
	while(i<N){
		while(check(i,j,from,type,rank)){
			from+=j-next[j];
			j=next[j];
		}
		i++,j++;
		if(j==K) nownum[from]=min(nownum[from],type);//若成功匹配,更新当前值
	}
}
void KMP(int rank){//测试排名rank对应每个斑点数的情况
	getnext(ranklis,K,next,rank);
	for(int i=0;i<N;i++) nownum[i]=INF;
	for(int i=1;i<=S;i++) KMP(i,rank);
	memcpy(realnum,nownum,(N+1)*sizeof(int));
}
vector<int> ans;
void work(void){
	for(int i=1;i<=R;i++) KMP(i);
	int B=0;
	for(int i=0;i+K<=N;i++) if(realnum[i]!=INF) B++,ans.push_back(i);
	printf("%d\n",B);
	for(int i=0;i<ans.size();i++) printf("%d\n",ans[i]+1);
}
void read(void){
	scanf("%d%d%d",&N,&K,&S);
	for(int i=0;i<N;i++) scanf("%d",&pattern[i]);
	memset(first,-1,sizeof(first));
	for(int i=0;i<K;i++){
		scanf("%d",&ranklis[i]);
		R=max(R,ranklis[i]);
		if(first[ranklis[i]]==-1) first[ranklis[i]]=i;
	}
}
int main(){
	freopen("cpattern.in","r",stdin);
	freopen("cpattern.out","w",stdout);
	read();
	work();
	return 0;
}