kmp008.txt

串的模式匹配的朴素算法是O(N^2)的, 可以 利用KMP(由D.E.Knuth, J.H.Morris, V.R.Pratt提出)算法改进至线性的算法. KMP算法与朴素算法的不同在于：处理"失配

算法如下：


/*
 
#include <iostream.h>
#include <string.h>
#include <iomanip.h>
 
int Index(char *, char *);
int KMP(char *, char *);
 
int main()
{
    char s[256] = "abcabaabcaccaaaabn";
    char *t[3] = {
        "abaabcac",
        "aaaab",
        "safasasf"
    };
 
    for (int i=0; i<3; i++) {
        cout<<"穷举的模式匹配: "<<Index(s, t[i])<<endl;
        cout<<"KMP算法: "<<KMP(s, t[i])<<endl;
        cout<<endl;
    }
 
    return 0;
}
 
int Index(char *s, char *t)
{
    int i = 0;
    int j = 0;
    int ls = strlen(s);
    int lt = strlen(t);
 
    while (i<ls && j<lt)
    {
        if (s[i] == t[j]) {
            i++;
            j++;
        }
        else {
            i = i - j + 1;
            j = 0;
        }
    }
 
    if (j >= lt) {
        return (i - lt);
    }
    else {
        return -1;
    }
}
 
int KMP(char *s, char *t)
{
    void GetNext(char *, int, int *);
 
    int *next = new int[strlen(t)];
    int lt = strlen(t);
    int ls = strlen(s);
    int i, j;
 
    GetNext(t, lt, next);
    i = j = 0;
    while (i<ls && j<lt)
    {
        if (j==-1 || s[i]==t[j]) {
            i++;
            j++;
        }
        else {
            j = next[j];
        }
    }
 
    if (j >= lt) {
        return (i - lt);
    }
    else {
        return -1;
    }
}
 
void GetNext(char *t, int lt, int *next)
{
    int i, j;
 
    if (lt > 0) { next[0] = -1; }
    j = -1;
    i = 0;
    while (i < lt)
    {
        if (j==-1 || t[i]==t[j]) {
            i++;
            j++;
            if (t[i] == t[j]) {
                next[i] = next[j];
            }
            else {
                next[i] = j;
            }
        }
        else {
            j = next[j];
        }
    }
 
    cout<<"Next 数组: "<<endl;
    for (i=0; i<lt; i++) cout<<setw(4)<<t[i];
    cout<<endl;
    for (i=0; i<lt; i++) cout<<setw(4)<<next[i];
    cout<<endl;
}
 
*/

示例：

/*穷举的模式匹配: 3
Next 数组:
   a   b   a   a   b   c   a   c
  -1   0  -1   1   0   2  -1   1
KMP算法: 3
 
穷举的模式匹配: 12
Next 数组:
   a   a   a   a   b
  -1  -1  -1  -1   3
KMP算法: 12
 
穷举的模式匹配: -1
Next 数组:
   s   a   f   a   s   a   s   f
  -1   0   0   0  -1   0   2   1
KMP算法: -1
 
Press any key to continue
*/