大體題意：

給你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