/*该篇文章所描述的方法是在《KMP改进算法之一》的基础上产生的，此篇文章主要扩展了KMP算法对于不能处理的如下情况：
主串：abcabcabd
子串：abcab
原先的KMP算法的结果：只能发现一处，即在开始部分匹配到的abcab；
改进后的KMP算法，可以发现两处：
开头位置的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==len
k=next[j-1];
while(k>-1 && match[k]!=match[j-1])k=next[k];
if(j==len){//将j==len时得到的结果存入到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];//多了一个尾部结点
getNext(match,pn,len_match,pn+len_match);//传递了尾部结点
int j=0;
while(*text!=0){
if(*text==match[j]){
text++;
j++;
if(j==len_match)
{
cout<<text-len_match<<endl;
j=pn[j];//利用了插入到尾部的新结点
}
}else{
j=pn[j];
if(j==-1){
text++;
j=0;
}
}
}
delete [] pn;
}
void main(){
char *match="abcab";
char *text="dfdabcabcabdd";
match_string(match,text);
}
/*输出结果：
abcabcabdd
abcabdd
*/