Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## AC

Posted by OZY123 at 2016-04-01 14:04:18 on Problem 3167
```KMP好题，感谢http://blog.csdn.net/xiaoxiaoluo/article/details/7475857与http://www.cppblog.com/zxb/archive/2010/10/06/128782.aspx?opt=admin
#include<cstdio>
#include<cstring>
const int N=250100;
const int M=1000100;
int n,m,s;
int a[N],b[M];
int hash[300],low[N],high[N],f[N];
int ans_num,ans[M];
bool check (int *a,int *b,int k)
{
if(b[hash[a[k]]]!=b[k])
return false;
if(low[k]>=0&&b[low[k]]>=b[k])
return false;
if(high[k]>=0&&b[high[k]]<=b[k])
return false;
return true;
}
void make ()
{
int i=1,j=-1;
f[0]=-1;
for (;i<m;i++)
{
while (j!=-1&&check(b,b+i-j-1,j+1)==false) j=f[j];
if (check(b,b+i-j-1,j+1)==true) j++;
f[i]=j;
}
return ;
}
void get_ans()
{
int i=0,j=-1;
for (;i<n;i++)
{
while (j!=-1&&check(b,a+i-j-1,j+1)==false) j=f[j];
if (check(b,a+i-j-1,j+1)==true) j++;
if (j+1>=m)
{
ans_num++;
ans[ans_num]=i-j+1;
j=f[j];
}
}
return ;
}
int main()
{
ans_num=0;
scanf("%d%d%d",&n,&m,&s);
for (int u=0;u<n;u++)
scanf("%d",&a[u]);
memset(hash,-1,sizeof(hash));
hash[0]=hash[s+1]=-2;
for (int u=0;u<m;u++)
{
scanf("%d",&b[u]);
if (hash[b[u]]==-1)
hash[b[u]]=u;
int i;
for (i=b[u]-1;hash[i]==-1;i--);
low[u]=hash[i];
for (i=b[u]+1;hash[i]==-1;i++);
high[u]=hash[i];
}
make();
get_ans();
printf("%d\n",ans_num);
for (int u=1;u<=ans_num;u++) printf("%d\n",ans[u]);
return 0;
}```

Followed by: