hdu5918（KMP求匹配的次数）

题意：分别给出长度为n,m的正整数序列a,b,问a中有多少个起点q,满足从q开始,间隔为p，长度为m的子序列能和b匹配

思路：拆成p个串，跑p次kmp。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000005;
int n,m,p,fail[maxn];
void get_fail( int* P,int *f ){
    f[0] = -1;
    for( int i = 1;i < m;i++ ){
        int j = f[i-1];
        while( j != -1 && P[j+1]!=P[i] )j = f[j];
        if( P[j+1]==P[i] ) f[i] = j+1;
        else f[i] = -1;
    }
}
int cnt = 0;
void find( int s,int*T,int* P,int* f ){
    int j = -1;
    for( int i = s;i < n;i += p ){
        while( j != -1 && P[j+1] != T[i] ) j = f[j];
        if( P[j+1]==T[i] )j++;
        if( j == m-1 ) {
            cnt++;j = f[j];  // 求匹配个数需要加这句话
        }
    }
}
int a[maxn],b[maxn];
int main(){
    int T,ca = 0;
    scanf("%d",&T);
    while(T--){
        cnt = 0;
        scanf("%d%d%d",&n,&m,&p);
        for( int i = 0; i < n;i++ ){
            scanf("%d",&a[i]);
        }
        for( int i = 0;i < m;i++ )scanf("%d",&b[i]);
        get_fail( b,fail );
        int mn = min( n,p );
        for( int i = 0;i < mn;i++ ){
            find( i,a,b,fail );
        }
        printf("Case #%d: %d\n",++ca,cnt);
    }
    return 0;
}