【字符串匹配】 KMP算法与BM算法的简单c++代码实现

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

class Solution {
public:

    void Getnext(string t,int l,vector&next){//获取优化next数组
        int j=0,k=-1;
        next[0]=-1;
        while(jnext(l);
        Getnext(pattern,l,next);

        int i=0,j=0;
        while(i=l)return i-l;
        else return -1;

    }

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

        //构造坏字符跳转规则
        vectorskip1(26);
        for(int i=0;i<26;i++)skip1[i]=l;
        for(int i=0;iskip2(l);//跳转数组
        vectorpre(l);//包含后缀位置数组
        for(int i=0;i0; 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=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);

    }


};