C++实现KMP算法

    #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
特别注意：本站所有转载文章言论不代表本站观点！
本站所提供的图片等素材，版权归原作者所有，如需使用，请与原作者联系。