大体题意：

给你a数组和b 数组和p，问有多少个子序列，aq,a(q+p),a(q+2p).,., 完全等于b 数组。

思路：

两个数组最大是1e6.

又是字符串匹配问题，首先想到kmp算法。

这个题目里面b 数组是固定的，直接获得b 的next数组。

然后我们划分成p 个a数组，这p 个字符串分别与b 数组进行匹配即可。

吐槽：

当然还在想万一模板串比查找串的长度小，或者大怎么办，我还写了两个kmp  但是是错的。

想一想就知道  如果a数组比b 数组短的话，这个解肯定是0， 那么直接写一个kmp就好了。

#include <cstdio>#include <cstring>#include <algorithm>#include <vector>#define Siz(x) (int)x.size()using namespace std;const int maxn = 1000000 + 7;int T, n, m, p, ks;int a[maxn], b[maxn], Next[maxn];vector<int>c[maxn];void get_Next(){    memset(Next,0,sizeof Next);    int j = 0;    for (int i = 1; i < m; ++i){        while(j > 0 && b[i] != b[j]) j = Next[j];        if (b[i] == b[j]) ++j;        Next[i+1] = j;    }}int Kmp(int id,int sz){    int j = 0;    int ans = 0;    for (int i = 0; i < sz; ++i){        while(j > 0 && b[j] != c[id][i]) j = Next[j];        if (b[j] == c[id][i])++j;        if (j == m) ++ans;    }    return ans;}int main(){    scanf("%d",&T);    while(T--){        scanf("%d %d %d",&n, &m, &p);        for (int i = 0; i < p; ++i)c[i].clear();        for (int i = 0; i < n; ++i) {            scanf("%d",a+i);            c[i%p].push_back(a[i]);        }        for (int i = 0; i < m; ++i) scanf("%d",b+i);        b[m] = 0;        get_Next();        int ans = 0;        for (int i = 0; i < p; ++i){            if (Siz(c[i]) > 0) ans += Kmp(i,Siz(c[i]));        }        PRintf("Case #%d: %d/n",++ks,ans);    }    return 0;}/**1 3 111 1 13 1 11 1 11**/
Sequence I
Time Limit: 3000/1500 MS (java/Others)    Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 1579    Accepted Submission(s): 589Problem DescriptionMr. 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. InputThe 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). OutputFor 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
26 3 11 2 3 1 2 31 2 36 3 21 3 2 2 3 11 2 3 Sample Output
Case #1: 2Case #2: 1 Source2016中国大学生程序设计竞赛（长春）-重现赛 Recommendwange2014   |   We have carefully selected several similar problems for you:  6014 6013 6012 6011 6010