C++实现KMP算法

2018-07-20    来源:open-open

容器云强势上线!快速搭建集群,上万Linux镜像随意使用

    #include <iostream>  
    #include <stdlib.h>  
    #include <vector>  
    using namespace std;  
    void NEXT(const string &T, vector<int> &next)  
    {  
        //按模式串生成vector,next(T.size())     
        next[0] = -1;  
        for(int i = 1; i < T.size(); i++)  
        {  
            int j = next[i - 1];  
            while(T[i] != T[j + 1] && j >= 0)  
                j = next[j];  
            //递推计算  
            if(T[i] == T[j + 1])  
                    next[i] = j + 1;  
            else  
                    next[i] = 0;  
        }  
    }  
    string::size_type COUNT_KMP(const string &S, const string &T)  
    {  
        //利用模式串T的next函数求T在主串S中的个数count的KMP算法  
        //其中T非空,  
        vector<int>   next(T.size());  
        NEXT(T, next);  
        string::size_type index, count=0;  
        for(index=0; index < S.size(); ++index)  
        {  
            int pos=0;  
            string::size_type iter = index;  
            while(pos < T.size() && iter<S.size())  
            {     
                if(S[iter] == T[pos])  
                {  
                    ++iter;  
                    ++pos;  
                }  
                else  
                {  
                    if(pos == 0)  
                        ++iter;  
                    else  
                        pos = next[pos - 1] + 1;  
                }  
            }  
            if(pos == T.size() && (iter - index) == T.size())  
                ++count;  
        }  
        return count;  
    }  
    int main()  
    {  
          
        string S, T;  
        cout<<"请输入主串(参照的)"<<endl;  
        cin>>S;  
        cout<<"请输入子串(要查找的)"<<endl;  
        cin>>T;  
        string::size_type count =COUNT_KMP(S,T);  
        cout<<"一共有 "<<count<<" 个子串"<<endl;  
        return 0;  
    }  

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点!
本站所提供的图片等素材,版权归原作者所有,如需使用,请与原作者联系。

上一篇:一个更改 hosts 的 PHP 脚本

下一篇: jdbc 使用PreparedStatement来存储和读取大数据(Blob或Clob)