[分析]

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现。其算法复杂度为O(n+m)，相对于朴素的O(n^2)算法有显著的改进。

KMP的算法核心在于构造匹配数组，利用匹配数组来处理失配过程。每当失配的时候，我们检查匹配串的待匹配点之前，是否存在相同的前缀和后缀，对于某个相同的前缀和后缀，它一定同时在匹配串和原串中同时出现。此时，我们可以将待匹配串前移到前缀位置的下一位继续匹配。这就是KMP的核心。

现在将分为两步叙述。一是如何够构造这个匹配数组，二是如何进行匹配过程。

匹配数组next[]构造：建立两个指针，i和j，首先把next[0]置为0。j=0,i=1; 如果j和i匹配，则next[i]=j+1，i++，j++；

否则，j=next[j - 1]，直到匹配或者j=0；此后如果匹配next[i]=j+1，否则next[i]=0；

接下来是一个构造实例：

初始：

j i

0 1 2 3 4 5

a b c a b y

0

失配：

j i

0 1 2 3 4 5

a b c a b y

0 0

失配：

j     i

0 1 2 3 4 5

a b c a b y

0 0 0

匹配：

j        i

0 1 2 3 4 5

a b c a b y

0 0 0 1

匹配：

j        i

0 1 2 3 4 5

a b c a b y

0 0 0 1 2

失配过程：

j           i

0 1 2 3 4 5

a b c a b y

0 0 0 1 2

失配：

j              i

0 1 2 3 4 5

a b c a b y

0 0 0 1 2 0

接下来是匹配过程。

KMP过程：设置指针i,j分别指向原串和模式串。原串和模式串逐一匹配；

如果匹配，i++,j++。如果j==patten.length()，返回i。

如果失配，j=next[j-1]直到i指向的字符和j指向的字符匹配，如果j==0且仍然失配，则i++。

接下来是一个匹配实例：

i

0 1 2 3 4 5 6 7 8 9 10 11

a b x a b c  a b c a  b   y

j

0 1 2 3 4 5

a b c a b y

0 0 0 1 2 0

匹配：

i

0 1 2 3 4 5 6 7 8 9 10 11

a b x a b c  a b c a  b   y

j

0 1 2 3 4 5

a b c a b y

0 0 0 1 2 0

匹配：

i

0 1 2 3 4 5 6 7 8 9 10 11

a b x a b c  a b c a  b   y

j

0 1 2 3 4 5

a b c a b y

0 0 0 1 2 0

失配过程：

i

0 1 2 3 4 5 6 7 8 9 10 11

a b x a b c a b c a b y

j

0 1 2 3 4 5

a b c a b y

0 0 0 1 2 0

依然失配，放弃，i++：

i

0 1 2 3 4 5 6 7 8 9 10 11

a b x a b c  a b c a  b  y

j

0 1 2 3 4 5

a b c a b y

0 0 0 1 2 0

匹配：

i

0 1 2 3 4 5 6 7 8 9 10 11

a b x a b c  a b c a  b  y

j

0 1 2 3 4 5

a b c a b y

0 0 0 1 2 0

匹配：

i

0 1 2 3 4 5 6 7 8 9 10 11

a b x a b c  a b c a  b  y

j

0 1 2 3 4 5

a b c a b y

0 0 0 1 2 0

一直匹配：

i

0 1 2 3 4 5 6 7 8 9 10 11

a b x a b c a  b c a  b   y

j

0 1 2 3 4 5

a b c a b y

0 0 0 1 2 0

出现失配：

i

0 1 2 3 4 5 6 7 8 9 10 11

a b x a b c  a b c a  b   y

j

0 1 2 3 4  5

a b c a b  y

0 0 0 1 2  0

失配过程：

i

0 1 2 3 4 5 6 7 8 9 10 11

a b x a b c  a b c a  b   y

j

0 1 2 3 4  5

a b c a b  y

0 0 0 1 2  0

也就是说，在j=5对应的y之前，有长度为2的前缀和后缀匹配，我们直接从这个前缀后面接着匹配就行了。

一直匹配：

i

0 1 2 3 4 5 6 7 8 9 10 11

a b x a b c  a b c a  b   y

j

0 1 2 3 4  5

a b c a b  y

0 0 0 1 2  0

j==6，匹配成功，返回i。

以上是KMP算法构造和实现过程。

[代码]

#include<bits/stdc++.h>
#define DE cout << "------" << endl
#define mems(a, b) memset(a, (b), sizeof a)
using namespace std;
typedef long long ll;
typedef long double ld;

char a[10007], p[107];
int nxt[107];

int lena, lenp;

void GetNext(char p[], int len){
    int i = 1, j = 0;
    nxt[0] = 0;
    while(i < len){
        if(p[i] == p[j]){
            nxt[i] = j + 1;
            i++, j++;
        }
        else{
            while(p[i] != p[j] && j > 0) j = nxt[j - 1];
            if(p[i] == p[j]) nxt[i] = j + 1, i++, j++;
            else nxt[i] = 0, i++;
        }
    }
    for(int i = 0; i < len; i++) cout << nxt[i] << ' ';cout << endl;
}

int KMP(char a[], char p[], int lena, int lenp){
    int i = 0, j = 0;
    while(i < lena){
        if(a[i] == p[j]){
            i++, j++;
            if(j == lenp) return i;
        }
        else{
            while(a[i] != p[j] && j > 0) j = nxt[j - 1];
            if(a[i] == p[j]) i++, j++;
            else i++;
        }
    }
    return -1;
}

//abxabcabcaby
//abcaby

int main(){
    scanf("%s", a);
    scanf("%s", p);
    lena = strlen(a), lenp = strlen(p);
    GetNext(p, lenp);
    int ans = KMP(a, p, lena, lenp);
    if(ans != -1) cout << "Matched at position " << ans - lenp << endl;
    else cout << "Can't Match";
}

举例：HDU-1711

#include<bits/stdc++.h>
#define DE cout << "------" << endl
#define mems(a, b) memset(a, (b), sizeof a)
using namespace std;
typedef long long ll;
typedef long double ld;

int a[1000007], p[10007];
int nxt[10007];

int lena, lenp;

void GetNext(int p[], int len){
    int i = 1, j = 0;
    nxt[0] = 0;
    while(i < len){
        if(p[i] == p[j]){
            nxt[i] = j + 1;
            i++, j++;
        }
        else{
            while(p[i] != p[j] && j > 0) j = nxt[j - 1];
            if(p[i] == p[j]) nxt[i] = j + 1, i++, j++;
            else nxt[i] = 0, i++;
        }
    }
    //for(int i = 0; i < len; i++) cout << nxt[i] << ' ';cout << endl;
}

int KMP(int a[], int p[], int lena, int lenp){
    int i = 0, j = 0;
    while(i < lena){
        if(a[i] == p[j]){
            i++, j++;
            if(j == lenp) return i;
        }
        else{
            while(a[i] != p[j] && j > 0) j = nxt[j - 1];
            if(a[i] == p[j]) i++, j++;
            else i++;
        }
    }
    return -1;
}

//abxabcabcaby
//abcaby

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&lena,&lenp);
        for(int i = 0; i < lena; i++) scanf("%d",&a[i]);
        for(int i = 0; i < lenp; i++) scanf("%d",&p[i]);
        GetNext(p, lenp);
        int ans = KMP(a, p, lena, lenp);
        if(ans == -1) printf("-1\n");
        else printf("%d\n",ans-lenp+1);
        //if(ans != -1) cout << "Matched at position " << ans - lenp << endl;
        //else cout << "Can't Match";
    }
}

文章出得很快，有很多细节考虑可能不充分，欢迎指出，互相学习。