hdu1711(终于搞懂了KMP算法了。。)

题意：给你两个长度分别为n(1 <= N <= 1000000)和m(1 <= M <= 10000)的序列a[]和b[]，求b[]序列在a[]序列中出现的首位置。如果没有请输出-1。

这题用裸KMP算法O（N）水过～

KMP算法的两个函数：

Code(hdu1711):

#include <stdio.h>

#include <string.h>

const int maxn = 1000005;

const int maxm = 10005;

int a[maxn], b[maxm], next[maxm];

int n, m;

void Read()

{

    int i;

    scanf("%d%d",&n, &m);

    for(i=0; i<n; i++) scanf("%d", &a[i]);

    for(i=0; i<m; i++) scanf("%d", &b[i]);

}

void Get_Next()

{

    int i, j;

    i = 0;

    next[0] = -1;

    j = -1;

    while(i<m) {

        if(j==-1||b[i]==b[j]) {

            i++;

            j++;

            next[i] =j;

        } else {

            j = next[j];

        }

    }

}

int Kmp()

{

    int i, j;

    i = 0;

    j = 0;

    while(i<n&&j<m) {

        if(j==-1||b[j]==a[i]) {

            i++;

            j++;

        } else {

            j=next[j];

        }

    }

    if(j>=m)

        return i - j + 1;

    else

        return -1;

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--) {

        Read();

        Get_Next();

        int ans = Kmp();

        printf("%d\n",ans);

    }

    return 0;

}