字符串

社交, 检索, 标签云

字符串 零个或多个字符组成的有限序列.

  • 一般用单引号或双引号加以界定.
  • 特殊字符串 空串(长度为0); 空格串.
  • 子串, 真子串 类比集合.
  • 字符集 多个字符的集合. ASCII, GB2312, GBK, BIG5, GB18030, Unicode等.
  • 性质:
    • 有限序列性
    • 可比性
  • 字符串字串判断: a in S
  • 求子串: S[start: end: step]
  • 连接: S1 + S2 或 ''.join(S1, S2)
  • 字符串是不可变类型.
  • 正则表达式 模式匹配, 搜索功能, 替换, 分割.

队列

FIFO (First In First Out)

队列 先进先出的线性表. 插入→队尾 删除→队首

  • 先进先出, 后进后出
  • 有限序列性
  • 建队 que = [""] * n head tail 表示头尾
  • 出入队:
    • 出:
      • 判断空: head == tail
      • 出: x = que[head] head = head + 1
    • 入: que[tail] = x tail = tail + 1
  • 循环队列 解决假溢出(在自加后求余)
  • queue 模块

栈

LIFO (Last In First Out)

栈 后进先出的线性表. 操作端→栈顶 非操作端→栈底

  • 先进后出, 后进先出
  • 有限序列性
  • 建栈 stack = [""] * n top 表示栈顶
  • 入栈: stack[top] = x top = top + 1
  • 出栈:
    • 判断空: top == -1
    • 出: x = stack[top] top = top - 1
  • 链栈 利用链式存储的栈. 空间利用率高, 但要额外的指针空间.

栈与队列

栈和队列的实现在仓库的这里.

这两个数据结构的实现很简单, 就不赘述了.

串

我也不知道为什么非要翻译成串，String直接翻译成字符串也完全没问题啊。

因为C++标准库<string>对字符串的实现已经很完善了，这里就不进行自己的实现了。我们主要集中看字符串的模式匹配算法。

另外，书上的串索引从1开始，而本博客永远只会使用从0开始的索引。

BF 算法

BF算法是暴力匹配算法，它的时间复杂度为O(n*m)，其中n是主串的长度，m是模式串的长度。

核心思想就是遍历每一个位置，然后比较每一个字符。

KMP 算法

KMP算法是Knuth-Morris-Pratt算法的简称，它的时间复杂度为O(n+m)，其中n是主串的长度，m是模式串的长度。

核心思想是计算最大公共前后缀长度，然后根据这个长度来计算出下一次匹配的位置。

具体的代码我将实现在另外一篇blog中。