比赛 |
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;
}