第五章 串

思维导图

串.png

重点问题

1，什么是串？

2，串的比较，比较的是什么？

3，常用的两种字符编码和两者间的差别？

4，串的存储结构

5， 关于串的算法

5.1 朴素的算法时间复杂度？（准确复杂度）

5.2 KMP算法时间的核心思想和时间复杂度？

5.3 KMP算法中的next数组元素的含义及作用？

5.4 KMP算法中的nextval数组元素的含义及作用？

---

1，什么是串？

由零个或多个字符组成的有限序列，又叫字符串。

2，串的比较，比较的是什么？

串的比较是通过组成串的字符之间的编码进行的。

3，常用的两种字符编码和两者间的差别？

为了和ASCII兼容，Uniconde的前256个字符与ASCII完全相同

4，串的存储结构

• 串的顺序存储结构
  用一组地址连续的存储单元来存储串中的字符序列。
• 串的链式存储结构
  与线性表的链式存储结构类似。
  串结构中的一个结点可以放一个字符也可以放多个字符。

5， 关于串的算法

5.1 朴素的算法时间复杂度？（准确复杂度）

O((n-m+1）* m)

5.2 KMP算法时间的核心思想和时间复杂度？

• 核心思想
  比较过的字符串不再比较
  1，子串T首个字符与后面的的串任意一个字符都不相等。
  2，子串T与主串S的前n为相等。
  3，子串T的首字符不可能与主串S的前n为相等。
• 时间复杂度
  O(n+m)

5.3 KMP算法中的next数组元素的含义及作用？

next数组中元素的含义：已匹配的字符数前缀和后缀相最大的相同长度 + 1 。
移动位数 = 已匹配的字符数 - 对应的部分匹配值。

5.4 KMP算法中的nextval数组元素的含义及作用？

可以用next[1]的值去取代它相等的字符后续next[j]的值。
1，算出next 值。
2，a位字符 的next值，next[a] 位的字符b的next值 比较。