大话数据结构读后感（二）串

5.2 串的定义

5.3 串的比较 strcmp();

5.6 朴素的模式匹配算法      //KMP模式匹配算法

　　int  Index（String S , Sring T , int pos）

　　{

　　　　int  i=pos;

　　　　int j=0;

　　　　//int next[255];

　　　　//get_next(T,next);//KMP算法得到next数组；

　　　　while(i

　　　　{

　　　　　　if(S[i]==T[j])        //   ||   j==0;

　　　　　　{

　　　　　　　　++i;

 　　　　　　     ++j;

　　　　　　}

　　　　　　else

　　　　　　{

　　　　　　　　i=i-j+1; //i退回到上次匹配的首位的下一位；

　　　　　　　　j=0;    //子串退回到T的首位；

　　　　　　　　//j=next[j];  //j退回合适的位置，i不变；   KMP算法；

　　　　　　}

　　　　}

　　　　if(j>T.size())

　　　　{

　　　　　　return i-T.size();

　　　　}

　　　　else

　　　　　　return 0;

　　} 

next数组的推演；

　　void  get_next（Sting T，int *next）

　　{

　　　　int i,j;

　　　　i=1;

　　　　j=0;

　　　　next[1]=0;

　　　　while(i

　　　　{

　　　　　　if(j==0 || T[i]==T[j])

　　　　　　{

　　　　　　　　++i;

　　　　　　　　++j;

　　　　　　　　next[i]=j;

　　　　　　}

　　　　　　else

　　　　　　　　j=next[j];            // j回溯；

　　　　}

　　}

KMP算法的改进：

void  get_nextval (Sting T，int *next)

　　{

　　　　int i,j;

　　　　i=1;

　　　　j=0;

　　　　nextval[1]=0;

　　　　while(i

　　　　{

　　　　　　if(j==0 || T[i]==T[j])

　　　　　　{

　　　　　　　　++i;

　　　　　　　　++j;

　　　　　　　　//next[i]=j;

　　　　　　　　if(T[i]!=T[j]) //若当前字符与前缀字符不同，则当前的j为nextval在i位置的值；

　　　　　　　　{

　　　　　　　　　　nextval[i]=j;

　　　　　　　　}　　

　　　　　　　　else　　

　　　　　　　　　　nextval[i]=nextval[j];//如果与前缀字符相同则将前缀字符的nextval值赋值给nextval在i位置的值；

　　　　　　}

　　　　　　else

　　　　　　　　j=nextval[j];            // j回溯；

　　　　}

　　}