#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
*/