Problem Description

Mr. Frog has two sequences a1,a2,⋯,an and b1,b2,⋯,bm and a number p.
He wants to know the number of positions q such that sequence
b1,b2,⋯,bm is exactly the sequence aq,aq+p,aq+2p,⋯,aq+(m−1)p where
q+(m−1)p≤n and q≥1.

Input

The first line contains only one integer T≤100, which indicates the
number of test cases.

Each test case contains three lines.

The first line contains three space-separated integers 1≤n≤106,1≤m≤106
and 1≤p≤106.

The second line contains n integers a1,a2,⋯,an(1≤ai≤109).

the third line contains m integers b1,b2,⋯,bm(1≤bi≤109).

Output

For each test case, output one line “Case #x: y”, where x is the case
number (starting from 1) and y is the number of valid q’s.

Sample Input

2
6 3 1
1 2 3 1 2 3
1 2 3
6 3 2
1 3 2 2 3 1
1 2 3

Sample Output

Case #1: 2
Case #2: 1

思路

先说题意，有t组数据，给了n,m,p分别代表a串的长度，b串的长度，和需要间隔p个字符匹配，求的是在a串里面能找到几个隔p个匹配后的串和b串一样的。
也就是从a串中每隔p取字，有多少个可与b串匹配

我们在kmp的时候，让i+=p,这样可以实现间隔p个,所以我们遍历一下a串，从每一个下标间隔p个进行匹配，把总和加起来就行

代码

#include<cstdio>
#include<cstring>
#include<string>
#include<set>
#include<iostream>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define mod 10000007
#define debug() puts("what the fuck!!!")
#define ll long long
using namespace std;
const int N=1e6+20;
int t,n,m,p,q=1;
int a[N],b[N],nxt[N];
void get_next()
{
    int j=0,k=-1;
    nxt[0]=-1;
    while(j<m)
    {
        if(k==-1||b[j]==b[k])
            nxt[++j]=++k;
        else
            k=nxt[k];
    }
}
int kmp(int x)
{
    int i=x,j=0,ans=0;
    while(i<n)
    {
        if(j==-1||a[i]==b[j])
        {
            i+=p;
            j++;
        }
        else
            j=nxt[j];
        if(j==m)
        {
            ans++;
            j=nxt[j];
        }
    }
    return  ans;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    cin>>t;
    while(t--)
    {
        cin>>n>>m>>p;
        for(int i=0; i<n; i++)
            cin>>a[i];
        for(int i=0; i<m; i++)
            cin>>b[i];
        get_next();
        int ans=0;
        for(int i=0; i<p&&i<n; i++)
            ans+=kmp(i);
        cout<<"Case #"<<q++<<": "<<ans<<endl;
    }
    return 0;
}

最后

以上就是文艺荷花为你收集整理的HDU5918 Sequence I(kmp，间隔匹配)Problem DescriptionInputOutputSample InputSample Output思路代码的全部内容，希望文章能够帮你解决HDU5918 Sequence I(kmp，间隔匹配)Problem DescriptionInputOutputSample InputSample Output思路代码所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。