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;  
}  </pre>