计算机考研:数据结构常用算法解析(4)

2020-01-17 作者:调剂信息   |   浏览(80)

  第四章

  

  KMP算法和朴素的匹配算法的关键区别就是解决了主串指针i的回溯,原理如下:

  

  设主串S[]和模式串T[],如比较到模式串的第j个字符。 当主串指针i和模式串指针j比较时 ,说明他们前面的所有字符都已经对应相等了。而

  

  Next[j]=k的定义是T1T2…Tk-1==Tj-k+1Tj-k+2….Tj-1且k是最大了,没有更长的了。

  

  所以Si和Tj比较失败时Si和Tk去比较。不可能有 这种匹配的成功,因为S2S3…..Si-1= =T2T3……Tj-1,而T2T3….Tj-1是不等于T1T2….Tj-2。除非next[j]=j-1;因为next定义的是最长的。所以任何挪动小于next[j]的串的匹配都是不能成功的。直到Tnext[j]和S[i]相比是才是最早有可能成功的。

  

  Int KMP_Index(Sstring S,Sstring T,int pos)

  

  {

  

  i=pos;j=1;

  

  while(i

  

  {

  

  If(j=0S[i]=T[j])//j=0表示模式串已经退到起点了说明在这个位置彻底不可能了,

  

  { ++i; ++j; } //i必须下移,j回到1开始

  

  Else j=next[j];

  

  }

  

  T[0]) return i-T[0];

  

  Else return 0;

  

  }

  

  求next[j]的方法和原理

  

  设k=next[j];那么T1T2…Tk-1= =Tj-k+1……Tj-2Tj-1;

  

  若Tj= =Tk,那么T1T2…Tk-1Tk= =Tj-k+1……Tj-2Tj-1Tj;

  

  所以 next[j+1]=k+1=next[j]+1;且T1T2…Tk-1= =Tj-k+1……Tj-2Tj-1已经是

  

  最长的序列,所以k+1也是next[j+1]最长的

  

  若Tj不等于Tk,那么就需要重找了。即…..Tj-1Tj ?,

  

  T1T2….

  

  所以next[j+1]首先=k=next[j]; 即…..Tj-1Tj ?,

  

  T1T2…Tk-1.

  

  若不相等,则next[j+1]=next[k]; 即…..Tj-1Tj ?,

  

  T1T2….Tnext[k]-1

  

  直到找到这样的序列, 即…..Tj-1Tj ?,

  

  T1T2 ...To

  

  那么,next[j+1]=next[next[j]]=next[next[next[j]]]…..=o+1;

  

  Void get_next(Sstring T,int next[])

  

  {

  

  i=1; next[1]=0; j=0;//i表示当前求的next

  

  While(i

  

  {

  

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

  

  {

  

  ++i;

  

  ++j;

  

  next[i]=j;

  

  }

  

  Else j=next[j];

  

  }

  

  }

  

  因为 next[ ] 在匹配过程中,若T[ j ]=T[ next[j] ];那么当 S[i]不等于T[j],

  

  S[ i]肯定也不等于T[k= next[j] ];

  

  所以 S[i]应直接与T[next[k]]比较,而我们通过将next[j]修正

  

  为nextval[j]=next[next[j]];这样能使比较更少。

  

  Void get_nextval(Sstring T,int nextval[])

  

  {

  

  i=1; nextval[1]=0; j=0;

  

  while(i

  

  {

  

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

  

  {

  

  ++i;

  

  ++j;

  

  if(T[i]!=T[j])

  

  nextval[i]=j;

  

  else

  

  nextval[i]=next[j];

  

  }

  

  else

  

  j=nextval[j];

  

  }

  

  空格串是指__由空格字符(ASCII值32)所组成的字符串,其长度等于 空格个数____。

  

  在模试匹配KMP算法中所用失败函数f的定义中,为何要求p1p2……pf(j)为p1p2……pj两头匹配的真子串?且为最大真子串?

  

  失败函数(即next)的值只取决于模式串自身,若第j个字符与主串第i个字符失配时,主串不回溯, 模式串用第k(即next[j])个字符与第i个相比,有‘p1…pk-1’=‘pj-k+1…pj-1’,为了不因模式串右移与主串第i个字符比较而丢失可能的匹配,对于上式中存在的多个k值,应取其中最大的一个。这样,因j-k最小,即模式串向右滑动的位数最小,避免因右移造成的可能匹配的丢失。

  

  第4章节有关数据结构算法,上文中为大家作了分析,希望考生对于这些算法能够熟记于心,方便考试的应用和日后的实际操作,预祝大家都能够取得好成绩,加油!
更多详情请点击:计算机考研:数据结构常用算法解析汇总

本文由考研现场确认是去报考的学校吗_专业考研资讯_奋力得考研网发布于调剂信息,转载请注明出处:计算机考研:数据结构常用算法解析(4)

关键词: 调剂信息