首页  思维导图  详情

串_计算机数据结构考研

2020-07-07 13:38:50   2  举报





AI智能生成

串_计算机数据结构考研

数据结构

计算机

考研

大学教育

作者其他创作

大纲/内容

版权∈ 本人所有
严禁擅自转载和商用受法律保护

更新记录

2020.5.17 开坑
2020.5.19 增加KMP next数组和nextval数组的优化案例

串

特殊的线性表

0个或多个字符组成的有限序列

存储结构

块链存储

顺序储存

定长顺序储存

堆分配储存

串结构

基本操作

比较操作 —— 从前往后先出现大的就大且长串的前缀与短串相同时长串更大

比较操作的实现

定位操作的实现

求子串的实现

应用

朴素模式匹配算法

长度相同的子串依次对比有一个不同就舍弃

模式串长m 主串长n 匹配成功最好O(m) 匹配失败最好O(n-m+1)=O(n) 最坏O(nm)

KMP算法

主串指针 i 不回溯模式串指针 j=next[j] 回溯平均复杂度O(n+m)

next数组的手算方法

当第j个字符匹配失败，由前1~j-1个字符组成的串记为S 则next[j]=S的最长相等前后缀长度+1 特别的next[1]=0

模式串中提炼重复的子串若发现相同则记为长度n
next[1] 肯定是 0 next[2] 肯定是 1

模式串为abaabac
next[7]的计算，字符串第七位是c，将前面的6个字符，从头尾开始取5个组成子串比较，
如果不相等，则从首尾取4个字符组成子串进行比较，如下
5个字符的情况：abaab : baaba 不相等继续寻找
4个字符的情况：abaa : aaba 不相等继续寻找
3个字符的情况：aba : aba 此时相等，那么next[7] = 3+1 = 4
如果一直比较到最后一个字符都不相等，那么该next值为1

优化【减少模式串内相同元素的反复对比】

当子串和模式串不匹配时 j=nextval[j];
若发现相同元素则赋值前一个相同元素的next[j]

章节技巧

易错概念

字符在主串中的位置

第一次出现的位置

子串在主串中的位置

子串的第一个字符在主串中的位置

ex. IPhone 11 Pro → 11 Pro是8

空串

A="

空格串