串_计算机数据结构考研

串_计算机数据结构考研

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

更新记录

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

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

模式串为abaabacnext[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=\"

空格串

A=\"   \"

求子串操作

从串S中截取第i个字符起长度为l的子串

KMP算法 主串不回溯  主串的指针不会变小