记录编号	407266	评测结果	AAAAAAAAAA
题目名称	[USACO Dec05]可疑的斑点	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.222 s
提交时间	2017-05-20 22:23:17	内存使用	12.37 MiB

#include<cstdio>
#include<bitset>
using namespace std;
const int N=1e5+10;
int n,k,s,a[N],r[N];
bitset<N> dp[30][30],ok;
//dp[i][j]表示数字大小用到i,rank用到j时每一位合法性 
int nxt[N];
char S[N],T[N];
void kmp(){
	for (int i=2;i<=k;i++){
		int j=nxt[i-1];
		while (j&&T[j+1]!=T[i]) j=nxt[j];
		nxt[i]=(T[j+1]==T[i]?j+1:j);
	}
	ok.reset();
	T[k+1]=-1;
	for (int i=1,j=0;i<=n;i++){
		while (j&&T[j+1]!=S[i]) j=nxt[j];
		if (T[j+1]==S[i]) j++;
		if (j==k) ok[i-k+1]=1;
	}
}
int main()
{
	freopen("cpattern.in","r",stdin);
	freopen("cpattern.out","w",stdout);
	scanf("%d%d%d",&n,&k,&s);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	int maxr=0;
	for (int i=1;i<=k;i++){
		scanf("%d",&r[i]);
		maxr=max(maxr,r[i]);
	}
	for (int j=0;j<=s;j++)
	for (int i=1;i<=n;i++)
		dp[j][0][i]=1;
	for (int i=1;i<=s;i++)
	for (int j=1;j<=maxr;j++){
		for (int l=1;l<=n;l++) S[l]=(a[l]==i);
		for (int l=1;l<=k;l++) T[l]=(r[l]==j);
		kmp();
		dp[i][j]=(dp[i-1][j-1]&ok)|dp[i-1][j];
		/*ok=dp[i][j];
		printf("val=%d rank=%d\n",i,j);
		for (int i=1;i<=n;i++)
			if (ok[i]) printf("%d ",i);
		puts("");*/
	}
	int ans=dp[s][maxr].count();
	printf("%d\n",ans);
	for (int i=1;i<=n;i++)
		if (dp[s][maxr][i]) printf("%d\n",i);
	return 0;
}