美文网首页程序员
字符串匹配与KMP算法

字符串匹配与KMP算法

作者: burglar | 来源:发表于2017-07-26 11:55 被阅读0次

    1.朴素字符串匹配算法

    int naive_matcher_v1(string text,string pattern){
        int n=text.size();
        int m=pattern.size();
        int s,i;
        for(s=0;s<n-m+1;++s){
            for(i=0;i<m;++i){
                if(text[s+i]!=pattern[i]) break;
            }
            if(i==m) return s;
        }
        return -1;
    }
    int naive_matcher_v2(string text,string pattern){
        int n=text.size();
        int m=pattern.size();
        int i=0,j=0;
        while(i<n && j<m){
            if(text[i]==pattern[j]){
                ++i;++j;
            }else{
                i=i-j+1;j=0;    //shift=i-j,increase shift by 1
            }
        }
        if(j==m) return i-j;
        else return -1;
    }
    

    2.KMP算法

    求前缀函数

    int* prefix_function(string pattern){
        int n=pattern.size();
        int* next=new int[n];    //next[i]=0 for all i=0,1,...,n-1
        int i=1,j=0;
        while(i<n){
            if(pattern[i]==pattern[j]){
                next[i]=j+1;
                ++i;++j;
            }else{
                if(j>0){
                    j=next[j-1];
                }else{
                    next[i]=0;
                    ++i;
                }
            }
        }
        return next;
    }
    

    实现KMP算法

    int kmp(string text,string pattern){
        int* next=prefix_function(pattern);
        int i=0,j=0;
        while(i<text.size() && j<pattern.size()){
            if(text[i]==pattern[j]){
                ++i;++j;
            }else{
                if(j>0){
                    j=next[j-1];
                }else{
                    ++i;
                }
            }
        }
        if(j==pattern.size()){
            return i-j;
        }else{
            return -1;
        }
    }
    

    3.测试代码

    void display(int arr[],int n){
        for(int i=0;i<n;++i){
            cout<<arr[i]<<" ";
        }
        cout<<endl;
    }
    int main(){
        string pattern="acacabac";
        int n=pattern.size();
        int* next=new int[n];
        next=prefix_function(pattern);
        display(next,n);  //打印前缀函数值
        string text="acacbbcacacabacacdb";
        cout<<kmp(text,pattern)<<endl;
        cout<<naive_matcher_v1(text,pattern)<<endl;
        cout<<naive_matcher_v2(text,pattern)<<endl;
        return 0;
    }
    
    

    相关文章

      网友评论

        本文标题:字符串匹配与KMP算法

        本文链接:https://www.haomeiwen.com/subject/flbnkxtx.html