首页 25考研 在职考研 0元畅学 26考研

新东方在线 > 考研 > 计算机 > 考研计算机资料 > 正文

扫码加入训练营

牢记核心词

学习得礼盒

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

2013-12-10 15:48:15来源：新东方在线编辑

　　

　　数据结构是计算机考研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开始

考研公开课小程序

本文关键字: 计算机 考研 数据结构

上一页 1 2 3 下一页

考研英语核心词汇营

背词+听课+练习+督学，学习得礼盒

更多资料

添加班主任领资料

添加考研班主任
免费领取考研历年真题等复习干货资料

  • 1.打开手机微信【扫一扫】，识别上方二维码；
  • 2.添加班主任，可领取学习资料。
更多>>
更多内容
25考研 在职研 AI择校 去测评 领资料

关注新东方在线考研服务号

获得21考研真题及答案解析

1. 打开手机微信【扫一扫】，识别上方二维码；
2.点击【关注公众号】，获取资料大礼包。

考研资料大礼包

历年考研真题及答案解析下载

英语一 英语二 政治 数学一 数学二 数学三 西医综合 教育综合 心理学综合
立即下载
近10年考研真题及答案免费下载
更多>>
更多公开课>>
更多>>
更多资料
我要
反馈 返回
首页
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10