HDU1711 Number Sequence（KMP）

March 13, 2016

题目链接

KMP 模版题，求子串第一次出现的位置

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
using namespace std;
int n, m;
int next[10005];
int a[1000005], b[10005];

void kmp_pre(int x[],int m,int nextt[]){
    int i, j;
    j = nextt[0] = -1;
    i = 0;
    while(i < m){
        while(-1!=j && x[i]!=x[j])
            j = nextt[j];
        nextt[++i] = ++j;
    }
}

int KMP_Index(int x[], int m, int y[], int n){
    int i = 0, j = 0;
    kmp_pre(x, m, nextt);
    while(i < n && j < m){
        if(j == -1 || y[i] == x[j]){
            i++; j++;
        }
        else
            j = nextt[j];
    }
    if(j == m)
        return i-m;
    else
        return -1;
}

int main(){
    //freopen("a.txt", "r", stdin);
    int t; cin >> t;
    while(t--){
        int tem;
        scanf("%d %d", &n, &m);
        for(int i = 0; i < n; i++){
            scanf("%d", &a[i]);
        }
        for(int i = 0; i < m; i++){
            scanf("%d", &b[i]);
        }
        int ans = KMP_Index(b, m, a, n);
        if(ans == -1) cout << "-1" << endl;
        else cout << ans+1 << endl;
    }
    return 0;
}

Written by Armin Li , a venture capitalist. [Weibo] [Subscribe]