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