posts - 16, comments - 0, trackbacks - 0, articles - 0

KMP Algothrim C++ Implement

Posted on 2008-08-26 16:48 dengbo 阅读(352) 评论(0)  编辑 收藏 引用 所属分类: Data Struct
#include "stdafx.h"
#include 
<iostream>
using namespace std;

int KMP_Search(const char *,const char*,const int *);
void getNext(const char*,int*);
int _tmain(int argc, _TCHAR* argv[])
{
    
    
char S[50]="ABC ABCDAB ABCDABCDABDE";
    
char W[10]="ABCDABD";
    
int next[10];
    getNext(W,next);

    
int m = KMP_Search(W,S,next);
    cout
<<m<<endl;
   system(
"pause");
   
return 0;
}


int KMP_Search(const char *W,const char*S,const int * next)
{
    
int m=0,i=0,wlen = strlen(W);
    
while(m+i<strlen(S))
    
{
        
if(W[i] == S[m+i])
        
{    i++;
            
if(i==wlen)
                
return m;
        }

        
else
        
{
            m
=+ i - next[i];
            
if (i>0)
                i
=next[i];
        }

    }

}


void getNext(const char* S,int next[])
{
    
int pos=2,cnd=0;
    next[
0]=  -1;
    next[
1= 0;
    
    
while(pos<strlen(S))
    
{
        
if(S[pos-1== S[cnd]) 
        
{    
            next[pos] 
= cnd+1;
            pos
++;
            cnd
++;
        }

        
if(S[pos-1!= S[cnd] && cnd>0)
            cnd 
= next[cnd];
        
if (cnd == 0)
        
{
            next[pos] 
= 0;
            pos
++;
        }

    }

}



只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理