ZZULIOJ-2264——sequence

谁践踏了优雅 2022-04-12 13:48 123阅读 0赞

#                                              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;
    }