[C++知识库]【字符串匹配】 KMP算法与BM算法的简单c++代码实现

KMP算法使用了比较简洁的代码（Getnext与KMPfind），BM方法只是生搬硬套。。。

class Solution {
public:

    void Getnext(string t,int l,vector<int>&next){//获取优化next数组
        int j=0,k=-1;
        next[0]=-1;
        while(j<l-1)
        {
            if(k == -1 || t[j] == t[k])
            {
                j++;k++;
                if(t[j]==t[k])//当两个字符相同时，就跳过
                    next[j] = next[k];
                else
                    next[j] = k;
            }
            else k = next[k];
        }
    }

    int KMPfind(string target,string pattern){//KMP字符串匹配
        int l=pattern.size();
        int L=target.size();
        vector<int>next(l);
        Getnext(pattern,l,next);

        int i=0,j=0;
        while(i<L&&j<l){
            if(j==-1||target[i]==pattern[j]){
                i++;j++;
            }
            else j=next[j];
        }
        if(j>=l)return i-l;
        else return -1;

    }

    int BMfind(string target,string pattern){//BM算法的一种实现
        int l=pattern.size();

        //构造坏字符跳转规则
        vector<int>skip1(26);
        for(int i=0;i<26;i++)skip1[i]=l;
        for(int i=0;i<l;i++){
            skip1[pattern[i]-'a']=l-1-i;
        }

        //构造好后缀跳转规则
        vector<int>skip2(l);//跳转数组
        vector<int>pre(l);//包含后缀位置数组
        for(int i=0;i<l;i++)pre[i]=l;
        skip2[l-1]=1;

        int c=0;
        for(int i = l -1; i>0; i--){
            for(int j = 0; j < i; j++){
                if(pattern.substr(j,l-i)==pattern.substr(i,l-i)){
                    if(j == 0){c = l - i;pre[i-1]=-1;}
                    else{
                        if(pattern[i - 1] != pattern[j - 1])pre[i - 1] = j - 1;
                    }
                }
            }
        }

        for(int i = 0; i < l - 1; i++){
            if(pre[i] != l)skip2[i] = l - 1 - pre[i];
            else{
                skip2[i] = l - 1 - i + pre[i];
                if(c != 0 && l - 1 - i >= c)skip2[i] -= c;
            }
        }


        //开始匹配
        int i=l-1;//目标指针
        int j=l-1;//模式指针
        int L=target.size();
        while(i<L){
            while(j>=0&&(target[i]==pattern[j])){
                i--;j--;
            }
            if(j<0)return i+1;
            else{
                i+=max(skip1[target[i]-'a'],skip2[j]);
                j=l-1;
            }
        }


        return -1;
    }

    int strStr(string haystack, string needle) {
        if(needle=="")return 0;
        return KMPfind(haystack,needle);

    }


};