/*該篇文章所描述的方法是在《KMP改進(jìn)算法之一》的基礎(chǔ)上產(chǎn)生的，此篇文章主要擴(kuò)展了KMP算法對(duì)于不能處理的如下情況：
主串：abcabcabd
子串：abcab
原先的KMP算法的結(jié)果：只能發(fā)現(xiàn)一處，即在開始部分匹配到的abcab；
改進(jìn)后的KMP算法，可以發(fā)現(xiàn)兩處：
開頭位置的abcabcabd，和中間部分的abcabd。
*/
#include <iostream>
using namespace std;
struct Pair{
Pair(int i,int v):index(i),value(v),next(NULL){}
int index;
int value;
Pair* next;
};
void getNext(char *match, int next[], int len, int *ev=NULL){
Pair *phead=NULL;
next[0]=-1;
for(int j=1,k;j<=len;j++){//多了一步j(luò)==len
k=next[j-1];
while(k>-1 && match[k]!=match[j-1])k=next[k];
if(j==len){//將j==len時(shí)得到的結(jié)果存入到ev之中
if(ev!=NULL)
*ev=k+1;
break;
}
next[j]= k+1;
while(k>-1 && match[j]==match[k+1])k=next[k];
if(next[j]!=k+1){
Pair *p=new Pair(j,k+1);
p->next=phead;
phead=p;
}
}
while(phead!=NULL){
next[phead->index]=phead->value;
Pair *p=phead;
phead=phead->next;
delete p;
}
}
void match_string(char * match, char* text){
int len_match=strlen(match);
int *pn=new int[len_match+1];//多了一個(gè)尾部結(jié)點(diǎn)
getNext(match,pn,len_match,pn+len_match);//傳遞了尾部結(jié)點(diǎn)
int j=0;
while(*text!=0){
if(*text==match[j]){
text++;
j++;
if(j==len_match)
{
cout<<text-len_match<<endl;
j=pn[j];//利用了插入到尾部的新結(jié)點(diǎn)
}
}else{
j=pn[j];
if(j==-1){
text++;
j=0;
}
}
}
delete [] pn;
}
void main(){
char *match="abcab";
char *text="dfdabcabcabdd";
match_string(match,text);
}
/*輸出結(jié)果：
abcabcabdd
abcabdd
*/