记录编号	191703	评测结果	AAAAAAAAAA
题目名称	[USACO Dec05]可疑的斑点	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.471 s
提交时间	2015-10-08 18:28:20	内存使用	2.12 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<algorithm>
using namespace std;
const int SIZEK=25010,SIZEN=100010,maxn=0x7fffffff/2;
int real[SIZEN]={0};//每字符串与
int nowreal[SIZEN]={0};
int N,K,S,R=0;
int next[SIZEK],f[SIZEK],ranklist[SIZEK],P[SIZEN];
int ans[SIZEN]={0};
void read()
{
	scanf("%d%d%d",&N,&K,&S);
	for(int i=0;i<N;i++) scanf("%d",&P[i]);
	for(int i=0;i<K;i++)
	{		
		scanf("%d",&ranklist[i]);
		if(ranklist[i]>R) R=ranklist[i];
	}
}
void find(int type)
{
	next[0]=-1;
	for(int i=0;i<K;i++)
	{
		int j=next[i];
		while(j!=-1&&(ranklist[i]==type||ranklist[j]==type)&&ranklist[i]!=ranklist[j]) j=next[j];
		next[i+1]=++j;
	}
}
bool check(int i,int j,int from,int type,int rank)
{
	if(j==K) return 1;
	if(j==-1) return 0;
	if(type<=real[from]) return 1;
	if(ranklist[j]==rank&&P[i]!=type) return 1;
	if(ranklist[j]!=rank&&P[i]==type) return 1;
	return 0;
}
void KMP(int type,int rank)
{
	int j=0;
	int from=0;//从哪一位开始匹配
	for(int i=0;i<N;i++)
	{
		while(check(i,j,from,type,rank))
		{
			//cout<<i<<" "<<j<<" "<<from<<" "<<type<<" "<<rank<<endl;
			from+=j-next[j];
			j=next[j];
		}
		j++;
		if(j==K) nowreal[from]=min(nowreal[from],type);
	}
}
void match(int rank)
{
	find(rank);
	for(int i=0;i<=N;i++) nowreal[i]=maxn;
	for(int i=1;i<=S;i++) KMP(i,rank);
	for(int i=0;i<=N+1;i++) real[i]=nowreal[i];
}
void work()
{
	int tot=0;
	for(int i=1;i<=R;i++) match(i);
	for(int i=0;i<=N;i++) if(real[i]!=maxn) ans[++tot]=i;
	printf("%d\n",tot);
	for(int i=1;i<=tot;i++) printf("%d\n",ans[i]+1);
}
int main()
{
	freopen("cpattern.in","r",stdin);
	freopen("cpattern.out","w",stdout);
	read();
	//for(int i=0;i<=N;i++) cout<<P[i]<<" ";
	work();
	return 0;
}