Question

KMP算法，输三组主串S和模式串P，输出模式串的Next(j)函数值，及该P在S中的位置的定

求详细程序及解答 试编写一程序，实现KMP算法，输入三组主串S和模式串P，输出模式串的Next(j)函数值，以及该P在S中的位置的定位函数值，即序号值。其中S的长度为15~25,P的长度为5~8。

Answer 1

KMP算法查找串S中含串P的个数count
　　#include <iostream>
　　#include <stdlib.h>
　　#include <vector>
　　using namespace std;
　　inline 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; //
　　}
　　}
　　inline string::size_typeCOUNT_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;
　　}
　　}//while end
　　if(pos==T.size()&&(iter-index)==T.size())++count;
　　} //for end
　　return count;
　　}
　　int main(int argc, char *argv[])
　　{
　　string S="abaabcacabaabcacabaabcacabaabcacabaabcac";
　　string T="ab";
　　string::size_type count=COUNT_KMP(S,T);
　　cout<<count<<endl;
　　system("PAUSE");
　　return 0;
　　}