#include <iostream>
using namespace std;
//該結構體是一個(index,value)的值對
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){
Pair *phead=NULL;//存儲發生變異的值對的頭結點
next[0]=-1;
for(int j=1,k;j<len;j++){//依次填充next數組
k=next[j-1];//從next[j-1]出發，去遞推next[j]的值
while(k>-1 && match[k]!=match[j-1])k=next[k];//依次遞推
next[j]= k+1;//存儲next[j]的值
while(k>-1 && match[j]==match[k+1])k=next[k];
/*
這樣二次搜尋的目的是為了避免重復，分析如下：
記文本串中的當前失配字符為X，即X!=match[j];
如果根據next[j]找到的再次比較位置滿足match[j]=match[next[j]]=match[k+1]，
那么顯然有X!=match[k+1]，因此對于此種情況，找到的next[j]位置是無效的，需要繼續查找。
但是，找到的新結果不能覆蓋next[j]當前值，否則將影響了next[j]的含義（在模式串match中，
當前位置j之前的next[j]-1個字符完全等價于模式串頭部的next[j]-1個字符，且next[j]-1這個長度
已經最大，不能再繼續增長），將導致不能被后續的遞推過程利用。因此必須要臨時存放到其他
位置，考慮到這種情況出現的可能性較低，因此為其分配一個len長的數組存儲會
相當浪費空間，所以使用鏈表來做，鏈表的每個結點保存的是一個(index,value)的值對！
*/
if(next[j]!=k+1)//將新結果插入到鏈表頭結點之前，好處有如下兩點：
//1。不插入到尾部，而是插入到頭結點之前，可以避免每次插入之前對鏈表的遍歷搜尋
//2。還不必考慮頭結點是否為NULL
{
Pair *p=new Pair(j,k+1);
p->next=phead;
phead=p;
}
}
while(phead!=NULL){//依次將鏈表中的結點內容拿出來更新next數組
next[phead->index]=phead->value;
Pair *p=phead;//為了下面釋放資源
phead=phead->next;
delete p;
}
//next[0]=0;
/*
這幾行代碼完成了經典的KMP算法中對next數組的求解
//這個算法的關鍵之處：求next[j]，和match[j]沒有半點關系，
//卻和match[j-1]有著莫大的關系，關鍵就是檢查match[j-1]這個元素到底和遞推過程中的哪一個match[next[k]]相等
//也就是在考慮“到底j之前能有多少個元素依次與模式串頭部開始的字符一一匹配呢？”，最終的答案是next[k]+1，
//實則代表了j為之前有k個字符能與串頭部的k個字符一一匹配。
//這k個字符應該分成這樣一種結構 1+(next[k']-1)，這里k=next[k']，
//第一個1代表最終要確保成立的“match[j-1]=match[k]”，而“next[k']-1”代表著k'位置之前有k-1個字符與串頭部一一匹配
//而這句話完全可以等價于“代表著j-1位置之前有k-1個字符與串頭部一一匹配”，
//這句話很難理解，需要對照建立next數組的那個圖仔細研究一下，相信大家都能最終理解這句話。
//因此求解next[j]，我們只需關心兩件事既可：
//(1)在j-1這個位置上到底能不能為最終結果貢獻這個1
//(2)在(1)滿足的情況下，在j-1之前到底是多少個字符完全與串頭一一匹配，即為最終結果貢獻這個k-1
next[0]=-1;
for(int j=1,k;j<len;j++){
k=next[j-1];//遞推的起點
while(k>-1 && match[k]!=match[j-1] )k=next[k];//遞推的過程
next[j]= k+1;//遞推的結果
}
*/
}
void match_string(char * match, char* text){
int len_match=strlen(match);
int *pn=new int[len_match];
getNext(match,pn,len_match);
//第一種搜尋的方法
int j=0;
while(*text!=0){
if(*text==match[j]){
text++;
j++;
if(match[j]==0)
{
cout<<text-len_match<<endl;
j=0;
}
}else{
j=pn[j];
if(j==-1){
text++;
j=0;
}
}
}
/*
//第二種搜尋的方法
int i=0;
while(*text!=0){
if(i==len_match){
cout<<text-len_match<<endl;
i=0;
}
if(*text++==match[i++])continue;
else{
i=pn[i-1];
if(i==-1){i=0;continue;}
text--;
}
}*/
delete [] pn;
}
void main(){
char *match="abc";
char *text="aabcdabcabcxab";
match_string(match,text);
}
/*輸出結果為：
abcdabcabcxab
abcabcxab
abcxab
*/