NC15879. A Simple Problem
描述
输入描述
The first line contains two integers n and k(1≤n≤2×105,1≤k≤11), denoting the length of Yuyuan Rd andthe number of tree type..Next line consists of n integers ai (0≤ai<k), denotingthe sequence of tree type.Next line has only one integer m(1≤m≤100000).Next line contains m integers bi (0≤bi<k), denotingthe sequence Coach Yin remembered.
输出描述
The only integer in one line is the number of possible positions.
示例1
输入:
6 3 1 2 0 2 0 1 4 1 2 1 2
输出:
1
说明:
In the sample, it is possible that Coach Yin mistake type 2 with 1 and mistake type 0 with 2. So the original tree type is [2, 0, 2, 0]. As a consequence, the only possible position lies from the second tree to the 5-th tree.C++14(g++5.4) 解法, 执行用时: 47ms, 内存消耗: 2664K, 提交时间: 2018-05-09 21:43:56
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int maxn = 2e5+33;
int pre[13];
void f(int x[],int n,int m)
{
memset(pre,-1,sizeof pre);
for(int i=0;i<n;i++){
int now=x[i];
if(pre[x[i]]!=-1)
x[i]=i-pre[x[i]];
else
x[i]=-1;
pre[now]=i;
}
}
void prenxt(int x[],int nxt[],int m)
{
int i,j;
j=nxt[0]=-1;
i=0;
while(i<m)
{
while(j!=-1&&(j-x[i]<0?(x[j]!=-1):(x[i]!=x[j]))) j=nxt[j];
nxt[++i]=++j;
}
}
int kmp(int a[],int b[],int n,int m)
{
int nxt[maxn];
prenxt(b,nxt,m);
int i,j;
int ans=0;
i=j=0;
while(i<n){
while(j!=-1&&(j-a[i]<0?(b[j]!=-1):(a[i]!=b[j]))) j=nxt[j];
i++;j++;
if(j>=m){
ans++;
j=nxt[j];
}
}
return ans;
}
int main()
{
int a[maxn];
int b[maxn];
int n,k;
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++) scanf("%d",&a[i]);
int m;
scanf("%d",&m);
for(int i=0;i<m;i++) scanf("%d",&b[i]);
f(a,n,m);
f(b,m,m);
// for(int i=0;i<n;i++)
// printf("%d ",a[i]);
// printf("\n");
// for(int i=0;i<m;i++)
// printf("%d ",b[i]);
// printf("\n");
printf("%d\n",kmp(a,b,n,m));
}
C++11(clang++ 3.9) 解法, 执行用时: 45ms, 内存消耗: 2528K, 提交时间: 2018-05-29 20:10:49
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=2e5+9;
const int M=20;
int n,m,k;
int s[N],p[N],pre[M],c[N];
void init(int a[],int n)
{
memset(pre,-1,sizeof(pre));
for(int i=0;i<n;i++)
{
int now=a[i];
if(pre[now]!=-1)
a[i]=i-pre[a[i]];
else
a[i]=-1;
pre[now]=i;
}
}
void get()
{
int i=0,j=-1;
c[0]=-1;
while(p[i])
{
if(j==-1||( (j<p[i])?(p[j]==-1):(p[i]==p[j]) ) )
c[++i]=++j;
else{
j=c[j];
}
}
}
void kmp()
{
int ans=0;
int i=0,j=0;
get();
while(i<n&&j<m)
{
if(j==-1||((j<s[i])?(p[j]==-1):(s[i]==p[j])))
i++,j++;
else
{
j=c[j];
}
if(j==m)
{
ans++;
j=c[j];
}
}
printf("%d\n",ans);
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
{
scanf("%d",&s[i]);
}
scanf("%d",&m);
for(int j=0;j<m;j++)
{
scanf("%d",&p[j]);
}
init(s,n);
init(p,m);
kmp();
return 0;
}