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

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

　　

　　数据结构是计算机考研408计算机学科专业基础综合的重要组成部分，考生需要认真复习，尤其是对于数据结构中一些常用的算法问题，考生一定要弄懂弄会，理解的去掌握。小编下面一一为大家分析一下，帮助考生更好地去掌握。

　　第四章

　　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<=S[0]&&j<=T[0])

　　{

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

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

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