题目链接:
http://172.16.0.132/senior/#main/show/5437
题目:
题解:
发现满足上述性质并且仅当A序列的子序列的差分序列与B序列的差分序列相同
于是我们把A变成差分序列,把B变成差分序列,做一次KMP就好了
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std; const int N=1e6+;
int n,m;
int a[N],b[N],nxt[N];
inline int read(){
char ch=getchar();int s=,f=;
while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}
while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}
return s*f;
}
int main(){
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
n=read();m=read();
for (int i=;i<=n;i++) a[i]=read();
for (int i=;i<=m;i++) b[i]=read();
for (int i=;i<n;i++) a[i]=a[i+]-a[i];
for (int i=;i<m;i++) b[i]=b[i+]-b[i];
n--;m--;
nxt[]=;
for (int i=,j=;i<=m;i++){
while (j&&b[j+]!=b[i]) j=nxt[j];
if (b[j+]==b[i]) ++j;
nxt[i]=j;
}
int ans=;
for (int i=,j=;i<=n;i++){
while (j&&(j==m||b[j+]!=a[i])) j=nxt[j];
if (b[j+]==a[i]) ++j;
if (j==m) ans++;
}
printf("%d\n",ans);
return ;
}