【GDOI2021PJ Day2T1】杂音密码（noise）

Description

Input

Output

Sample Input

样例输入1：
7 3
0 2 1 1 7
2 2 7 3 5 0 1
2 1 2
样例输入2：
7 3
0 2 1 1 7
0 1 6 0 1 0 1
1 2 3

Sample Output

8

题解

考场不会KMP的痛
把混合序列和杂音序列一减（注意处理一下模数），就是一道KMP模板题了，直接拿密码序列去匹配即可
But我考场不会KMP+没处理模数痛失80

CODE

#include<cstdio>
#include<string>
#define max(a,b) (((a)>(b))?(a):(b))
#define min(a,b) (((a)<(b))?(a):(b))
#define R register int
#define N 100005
#define ll long long
#define mo 256
using namespace std;
inline void read(int &x)
{
	x=0;int f=1;char ch=getchar();
	while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();x*=f;
}
int t,m,mi[N],hun[N<<1],n[N<<1],next[N<<1],a,b,c,d,e,s[N<<1],ans,ans1[N<<1];
int main()
{
	freopen("noise.in","r",stdin);
	freopen("noise.out","w",stdout);
	read(t);read(m);read(a);read(b);read(c);read(d);read(e);
	for (R i=1;i<=t;++i)
	{
		if (i==1) n[i]=a;
		else n[i]=(((n[i-1]<<b)+(n[i-1]>>c))%mo+d)%mo%e;
	}
	for (R i=1;i<=t;++i)
		read(hun[i]);
	for (R i=1;i<=t;++i)
		s[i]=(hun[i]-n[i]+mo)%mo;
	for (R i=1;i<=m;++i)
		read(mi[i]);
	for (R i=2,j=0;i<=m;++i)
	{
		while (j && mi[j+1]!=mi[i]) j=next[j];
		if (mi[j+1]==s[i]) ++j;next[i]=j;
	}
	for (R i=1,j=0;i<=t;++i)
	{
		while (j && mi[j+1]!=s[i]) j=next[j];
		if (mi[j+1]==s[i]) ++j;
		if (j==m) ans1[++ans]=i-m+1,j=next[j];
	}
	if (!ans) printf("wrong\n");
	else
	{
		printf("%d\n",ans);
		for (R i=1;i<=ans;++i)
			printf("%d ",ans1[i]);
		printf("\n");
	}
	return 0;
}