严蔚敏《数据结构》配套辅导书(4-6章)【圣才出品】

圣才电子书www.100xuexi.com十万种考研考证电子书、题库视频学习平台（2）求子串——SUBSTR(sub,s,start,len)函数求子串的过程也是复制字符序列的过程，将s串中从第start个字符开始长度为len的字符序列复制到串sub中，即为求得的子串。（3）求子串位置的定位函数INDEX(s,t)。子串的定位操作通常称做串的模式匹配，就是求模式串（记为t）在主串（记为s）中的位置。算法的基本思想是：①从主串s的指定字符起和模式串t的第一个字符开始比较；②若相等，则继续逐个比较后续字符，直到t中每个字符依次和s中连续的一个字符序列相等，称匹配成功；③若不相等，则从主串s的下一个字符开始和t中的第一个字符开始继续比较，重复②③，直到s中字符比较结束，仍无法匹配称匹配不成功。【注意】简单模式匹配在最坏情况下的时间复杂度是O（n*m），n、m分别表示主串和模式串的长度。2．模式匹配的一种改进算法——KMP算法算法思想：在简单模式匹配的基础上，每当一趟匹配过程中出现字符比较不等时，不需回溯指示主串的指针i，而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较。其中“滑动”的距离只与模式串本身结构有关，且该距离实际上是找每个位置最长的公共前缀，把这个距离保存在一个数组中，并记该数组为next[1..n]。此外，在匹配过程中，失配时“滑动”的距离即next数组对应的值。next数组的定义为：6/186