HDU1711 Number Sequence

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;
const int maxn = 1000000+10;
const int maxm = 10000+10;

int gn, gm;
int a[maxn+5];
int b[maxm+5];
int f[maxm+5];

void getFail() {
    memset(f, 0, sizeof(f));
    f[0] = 0, f[1] = 0;
    int j = 0;
    for(int i = 1; i < gm; i++) {
        j = f[i];
        while(j && b[i]!=b[j]) j = f[j];
        if(b[i]==b[j]) {
            f[i+1] = j+1;
        } else {
            f[i+1] = 0;
        }
    }
}

void KM() {
    int j = 0;
    bool ok = false;
    for(int i = 0; i < gn; i++) {
        while(j && a[i]!=b[j]) j = f[j];
        if(a[i]==b[j]) j++;
        if(j==gm) {
            printf("%d\n", i-gm+2); 
            ok = true;
            break;
        }
    }
    if(!ok) printf("-1\n");
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &gn, &gm);
        for(int i = 0; i < gn; i++) {
            scanf("%d", &a[i]);
        }
        for(int i = 0; i < gm; i++) {
            scanf("%d", &b[i]);
        }
        getFail();
        KM();
    }
    return 0;
}

HDU1711 Number Sequence,布布扣,bubuko.com

HDU1711 Number Sequence

原文：http://blog.csdn.net/achiberx/article/details/22990807