Number Sequence HDU 1711（KMP）

http://acm.hdu.edu.cn/showproblem.php?pid=1711

首次接触KMP，自己都不是特别理解。在网上百度看了好几个帖子之后，对KMP也有了初步的理解。

#include <stdio.h>

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

void getnext( int n)

{

    int i=, j=-;

    next[]=-;

    while(i<n)

    {

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

            next[++i]=++j;

        else

            j=next[j];

        }

}

int KMP(int m, int n)

{

    int i=, j=;

    while(i<m)

    {

        while((j==- || a[i]==b[j]) && j<n)

            i++, j++;

        if(j==n) return i-n+;

        j=next[j];

    }

    return -;

}

int main()

{

    int T;

    scanf("%d", &T);

    while(T --)

    {

        int m, n;

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

        for(int i=; i<m; i++)

            scanf("%d", &a[i]);

        for(int i=; i<n; i++)

            scanf("%d", &b[i]);

        getnext( n);

        printf("%d\n", KMP(m, n));

    }

    return ;

}