KMP算法进行模式串匹配

第一步：定义定长的字符串数据结构

typedef struct {
    char ch[MAXLEN+1];
    int length;
}String;

第二步：KMP算法中的next[]数组

void Get_next(String T){
    int i = 1,j=0;
    Next[1] = 0;
    while(i < T.length){
        if(j == 0|| T.ch[i] == T.ch[j]){
            ++i;
            ++j;
            if(T.ch[i] != T.ch[j]) Next[i] = j;
            else Next[i] = Next[j];
        }
        else j = Next[j];       //难点，去给你们一个教程
    }
}

戳这里

第三部：模式串匹配：

int Index_KMP(String S , String T, int pos){
    int i = pos , j =1;
    while(i <= S.length && j <= T.length){
        if(j == 0||S.ch[i] == T.ch[j]) {++i;++j;}
        else j = Next[j];
    }
    if(j > T.length) return i - T.length;
    else return 0;
}

第四步main()函数

int main()
{
    string s,t;
    String S , T;
    cout << "请输入两个字符串" << endl;
    cin >> s >> t;
    S.length  = s.length();
    T.length = t.length();
    for(int i = 1 ;i <= S.length ;i++){
        S.ch[i] = s[i-1];
    }
    for(int i = 1 ;i <= T.length ;i++){
        T.ch[i] = t[i-1];
    }
    Get_next(T);
    cout << "请输入pos (求T 在主串 S中第pos 个字符之后的位置)"<<endl;
    int pos = 0;
    while(!(pos >=1 && pos <= S.length)){
        cin >> pos;
        if(!(pos >=1 && pos <= S.length)) cout << "输入错误,请重新输入:" << endl;
        else break;
    }
    int v = Index_KMP(S, T, pos);
    if(v) {
        cout <<"串T在S中第"<<pos<<"个字符之后第" <<v+1 - pos <<"个位置"<< endl;
    }
    else cout << "Matching failure" << endl;
}

完整代码：

#include<bits/stdc++.h>
#define MAXLEN 255
using namespace std;
const int maxn = 1e4;
int Next[maxn];
int Next1[maxn];
string s,t;
typedef struct {
    char ch[MAXLEN+1];
    int length;
}String;

int Index_KMP(String S , String T, int pos){
    int i = pos , j =1;
    while(i <= S.length && j <= T.length){
        if(j == 0||S.ch[i] == T.ch[j]) {++i;++j;}
        else j = Next[j];
    }
    if(j > T.length) return i - T.length;
    else return 0;
}
int Index_BF(String S, String T , int pos ){
    int i = pos , j = 1;
    while(i <= S.length && j <=T.length) {
        if(S.ch[i] == T.ch[j]) {++i ; ++j; }
        else {
            i = i-j+2;j=1;
        }
    }
    if(j > T.length) return i - T.length;
    else return 0;
}

void Get_next(String T){
    int i = 1,j=0;
    Next[1] = 0;
    while(i < T.length){
        if(j == 0|| T.ch[i] == T.ch[j]){
            ++i;
            ++j;
            if(T.ch[i] != T.ch[j]) Next[i] = j;
            else Next[i] = Next[j];
        }
        else j = Next[j];
    }
}
void Get_next0(String T){
    int i = 1; Next1[1] = 0; int j = 0;
    while(i < T.length){
        if(j ==0 || T.ch[i] == T.ch[j]){
            ++i;++j;Next1[i] = j;
        }
        else j = Next1[j];
    }
}
void Print(int v, int v1,int v2){
    cout<< "串s:" << s <<endl;
    cout<< "串t:" << t <<endl;
    if(v){
        cout << "简单匹配算法：" << endl;
        cout << "  t在s中的位置=" << v <<endl;
        cout <<"j        ";
        for(int i = 1; i < t.length()+1 ;i++){
            cout << i << " ";
        }
        cout << endl;
        cout <<"t[j]     ";
        for(int i = 1; i < t.length()+1 ;i++){
            cout << t[i-1] << " ";
        }
        cout << endl;
        cout <<"Next     ";
        for(int i = 1; i < t.length()+1 ;i++){
            cout << Next1[i] << " ";
        }
        cout << endl;
        cout <<"Nextval  ";
        for(int i = 1; i < t.length()+1 ;i++){
            cout << Next[i] << " ";
        }
        cout << endl;
        cout << "KMP算法：" << endl;
        cout << "  t在s中的位置=" << v1 <<endl;
        cout << "改进后的KMP算法：" << endl;
        cout << "  t在s中的位置=" << v1 <<endl;
    }
    else cout << "Matching failure" << endl;
}
int main()
{

    String S , T;
    cout << "请输入两个字符串" << endl;
    cin >> s >> t;
    S.length  = s.length();
    T.length = t.length();
    for(int i = 1 ;i <= S.length ;i++){
        S.ch[i] = s[i-1];
    }
    for(int i = 1 ;i <= T.length ;i++){
        T.ch[i] = t[i-1];
    }
    Get_next(T);
    Get_next0(T);
    cout << "请输入pos (求T 在主串 S中第pos 个字符之后的位置)"<<endl;
    int pos = 0;
    while(!(pos >=1 && pos <= S.length)){
        cin >> pos;
        if(!(pos >=1 && pos <= S.length)) cout << "输入错误,请重新输入:" << endl;
        else break;
    }
    int v = Index_KMP(S, T, pos);
    int v1 = Index_BF(S, T, pos);
    Print(v, v1, v1);
    return 0;
}