比赛 20170519 评测结果 AAWAWWAWWW
题目名称 可疑的斑点 最终得分 40
用户昵称 Arrow 运行时间 0.077 s
代码语言 C++ 内存使用 1.27 MiB
提交时间 2017-05-19 21:29:38
显示代码纯文本
#include<iostream>
#include<cstring>
#include<cstdio>
#define MAXN 100010
#define MAXK  25010
using namespace std;
	int n,s,k;
	int t[MAXN]={0},p[MAXK]={0};
	int next[MAXK]={0};
	int ans[MAXN]={0};
	int cnt=0;
bool check1(int x,int y)
{
	if((p[y]>p[y+1]&&p[x-1]>p[x])||(p[y]<p[y+1]&&p[x-1]<p[x])||(p[y]==p[y+1]&&p[x-1]==p[x]))
		return 1;
	else return 0;
}
void getnext()
{
	for(int i=2;i<k;i++)
	{
		int j=next[i-1];
		while(j&&!check1(i,j))
			j=next[j];
		if(check1(i,j))
			next[i]=j+1;
		else next[i]=0;
	}
}
bool check2(int x,int y)
{
	if(p[y]>p[y-1]&&t[x]>t[x-1]&&p[y]-p[y-1]<=t[x]-t[x-1])
		return true;
	else
		if(p[y]==p[y-1]&&t[x]==t[x-1])
			return true;
		else
			if(p[y]<p[y-1]&&t[x]<t[x-1]&&p[y-1]-p[y]<=t[x-1]-t[x])
				return true;
			else
				return false;
}
void KMP()
{
	int j=0,s=0;
	for(int i=0;i<n;i++)
	{
		if(!j)
		{
			s=1;
			j++;
			i++;
		}
		while(j&&!check2(i,j))
			j=next[j];
		if(j&&check2(i,j))
		{
			s++;
			j++;
		}
		if(s==k)
		{
			s=0;
			ans[cnt]=i-k+1;
			cnt++;
		}
	}
}
int main()
{
	freopen("cpattern.in","r",stdin);
	freopen("cpattern.out","w",stdout);
	scanf("%d",&n);scanf("%d",&k);scanf("%d",&s);
	for(int i=0;i<n;i++)
		scanf("%d",&t[i]);
	for(int i=0;i<k;i++)
		scanf("%d",&p[i]);
	getnext();
	KMP();
	printf("%d\n",cnt);
	for(int i=0;i<cnt;i++)
		printf("%d\n",ans[i]+1);
return 0;
}