zzuli 2264: sequence (初探KMP)

题目描述

给定一个含n个数的序列A和一个含m (m<=n) 个数的序列B。

询问在A中有多少段连续的长为m的子序列Ak,Ak+1,…,Ak+m-1使得对于任意1<=i, j<=m满足Ak+i-1-Bi=Ak+j-1-Bj

输入

第一行两个整数n，m (1 <=m <= n <= 106)

接下来一行n个整数，描述序列A (Ai <= 109)

接下来一行m个整数，描述序列B (Bi <= 109)

输出

输出一个数表示答案

样例输入

7 4 
6 6 8 5 5 7 4 
7 7 9 6 

样例输出

2

#include<stdio.h>
int a[1100000],b[1100000],next[1100000];
void GetNext(int *p,int *next,int n)
{
    int i=0,j=-1;
    next[0]=-1;
    while(i<n)
    {
        if(j==-1||p[i]==p[j])
        {
            i++;
            j++;
            next[i]=j;
        }
        else
            j=next[j];
    }
}
int kmp(int *a1,int *b1,int n,int m)
{
    int ans=0,i=0,j=0;
    while(i<n&&j<m)
    {
        if(a1[i]==b1[j]||j==-1)
        {
            i++;
            j++;
        }
        else
        {
            j=next[j];
        }
        if(j==m)
        {
            ans++;
            j=next[j];
        }
    }
    return ans;
}
int main()

{
    int n,m,i,j,f;
    scanf("%d%d",&n,&m);
    if(m==1)
    {
        printf("%d\n",n);
        return 0;
    }
    int a1[n-1],b1[m-1];
    for(i=0; i<n; i++) scanf("%d",a+i);
    for(i=0; i<m; i++) scanf("%d",b+i);
    m--;
    n--;
    for(i=0; i<m; i++) b1[i]=b[i+1]-b[i];
    for(i=0; i<n; i++) a1[i]=a[i+1]-a[i];
    GetNext(b1,next,m);
    printf("%d\n",kmp(a1,b1,n,m));
    return 0;
}