【HDU – 1711】Number Sequence【KMP】

【HDU – 1711】Number Sequence【KMP】

问题链接:https://vjudge.net/problem/HDU-1711

Solutiion:

模式匹配问题。b串是模式串,要在a串里找b。

关于KMP,详见:KMP (Knuth Morris Pratt) Pattern Searching

//
// Created by Undefined on 2018/7/17.
//

#include <iostream>

using namespace std;

const int SIZE = 1e6 + 10;
const int LIM = 1e4 + 10;             /* The maximum length of pattern string */
int kmp[LIM];
int txt[SIZE], pat[LIM];
int n, m;

void build() {
    kmp[0] = 0;
    int k = 0;
    int len = m;
    for (int i = 1; i < len; i++) {
        while (k > 0 && pat[k] != pat[i])
            k = kmp[k - 1];
        if (pat[k] == pat[i]) kmp[i] = ++k;
        else kmp[i] = 0;
    }
}

void kmpSearch() {
    build();
    int k = 0;
    int len = n;
    int pl = m;
    for (int i = 0; i < len; i++) {
        while (k > 0 && pat[k] != txt[i])
            k = kmp[k - 1];
        if (pat[k] == txt[i]) k++;
        else k = 0;
        if (k == pl) {
            printf("%d\n", i - k + 2);
            return;
        }
    }
    printf("-1\n");
}

int main(void) {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i++) scanf("%d", txt + i);
        for (int j = 0; j < m; j++) scanf("%d", pat + j);
        kmpSearch();
    }
    return 0;
}