Sequence I

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,⋯,bmis 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

题意：

　　给你a,b两个序列

　　和一个p ，求有多少个 q恰好满足 b1,b2,b3....bm 就是 a[q],a[q+p],a[q+2p]......a[q+(m-1)p];

题解：

　　将a序列，每隔p位置分成一组，这样最多有p组，个数和是n

　　将每组和b序列跑KMP计算答案

#include<bits/stdc++.h>

using namespace std;

#pragma comment(linker, "/STACK:102400000,102400000")

#define ls i<<1

#define rs ls | 1

#define mid ((ll+rr)>>1)

#define pii pair<int,int>

#define MP make_pair

typedef long long LL;

const long long INF = 1e18;

const double Pi = acos(-1.0);

const int N = 1e6+, M = 1e6, mod = 1e9+, inf = 2e9;

int T,n,m,p,s[N],t[N],ans = ;

vector<int > P[N];

int nex[N];

int main()

{

    int cas = ;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d%d",&n,&m,&p);

        for(int i = ; i <= n; ++i) scanf("%d",&t[i]);

        for(int i = ; i <= m; ++i) scanf("%d",&s[i]);

        for(int i = ; i < p; ++i) P[i].clear();

        memset(nex,,sizeof(nex));

        ans = ;

        int k = ;

        for(int i=; i<=m; i++)

        {

            while(k>&&s[k+]!=s[i]) k = nex[k];

            if(s[k+]==s[i])k++;

            nex[i] = k;

        }

        if(p == )

        {

            k = ;

            for(int i=; i<=n; i++)

            {

                while(k>&&s[k+]!=t[i]) k = nex[k];

                if(s[k+]==t[i]) k++;

                if(k==m) {

                    k = nex[k];

                    ans++;

                }

            }

            printf("Case #%d: ",cas++);

            printf("%d\n",ans);

        }

        else {

            for(int i = ; i <= n; ++i)

                P[i % p].push_back(t[i]);

            for(int i = ; i < p; ++i) {

                k = ;

                for(int j = ; j < P[i].size(); ++j) {

                    while(k>&&s[k+]!=P[i][j]) k = nex[k];

                    if(s[k+]==P[i][j]) k++;

                    if(k==m) {

                        k = nex[k];

                        ans++;

                    }

                }

            }

            printf("Case #%d: ",cas++);

            printf("%d\n",ans);

        }

    }

}

AQ

HDU 5918 Sequence I KMP

Sequence I