ZZULIOJ-2264——sequence

sequence

题目描述

给定一个含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 <= 10^6)

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

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

输出

输出一个数表示答案

样例输入

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

样例输出

题意描述：

判断一个主串中有多少段满足与子串的关系，A(k+i-1)-Bi=A(k+j-1)-Bj。

解题思路：

主串匹配模式串，KMP模板，关系式可进行转化A(k+i-1)-A(k+j-1)=Bi-Bj。将主串和模式串douj都进行处理得到相邻两个的差值，进行匹配。

程序代码：

#include<stdio.h>
int next[1000010];
int s1[1000010],s2[1000010];
int a[1000010],b[1000010];
void get_next(int s[],int len)
{
    int i,j;
    i=1;j=0;
    next[0]=0;
    while(i<len)
    {
        if(s[i]==s[j])
        {
            next[i]=j+1;
            i++;
            j++;
        }
        if(j==0&&s[i]!=s[j])
        {
            next[i]=0;
            i++;
        }
        if(j>0&&s[i]!=s[j])
            j=next[j-1];
    }
}
int kmp(int s1[],int len1,int s2[],int len2)
{
    int n,i,j;
    i=0;j=0;
    n=0;
    while(i<len1)
    {
        if(s1[i]==s2[j])
        {
            j++;
            if(j==len2)
            {
                n++;
                j=next[j-1];
            }
            i++;
        }
        if(j==0&&s1[i]!=s2[j])
            i++;
        if(j!=0&&s1[i]!=s2[j])
            j=next[j-1];
    }
    return n;
}
int main()
{
    int n,m,num,i,j,u;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        for(i=0;i<n-1;i++)
            s1[i]=a[i+1]-a[i];
        for(i=0;i<m;i++)
            scanf("%d",&b[i]);
        for(i=0;i<m-1;i++)
            s2[i]=b[i+1]-b[i];
        get_next(s2,m-1);
        num=kmp(s1,n-1,s2,m-1);
        printf("%d\n",num);
    }
    return 0;
}