串-数据结构第4章

术语:串长、空串、空格串、子串、主串、字符在主串中的位置、子串在主串中的位置；串，即字符串(String)是由零个或多个字符组成的有限序列。

第四章 串 数据结构 王道考研系列

• 串
  • 定义
    • 串，即字符串(String)是由零个或多个字符组成的有限序列
    • 术语:串长、空串、空格串、子串、主串、字符在主串中的位置、子串在主串中的位置
  • 串[VS]线性表
    • 串的数据对象限定为字符集
    • 串的基本操作大多以“子串”为操作对象
  • 基本操作
    • lndex(S,T)，定位操作,找到串T在主串S中的位置
    • StrCompare(S,T):比较操作。若S>T，则返回值>0;若S=T，则返回值=0;若S<T，则返回值<0。
    • 其他...
  • 字符集编码
    • 字符集
      • 英文字符―—ASClI字符集
      • 中英文―—Unicode字符集
    • 每个字符在计算机中对应一个二进制数，比较字符的大小其实就是比较二进制数的大小
• 串的存储结构
  • 顺序存储
    • 静态数组
    • 动态数组
      • malloc、free
  • 链式存储
    • 可让每个结点存多个字符，没有字符的位置用'#'或'\O'补足
  • 王道教材采用静态数组
  • 基于顺序存储实现基本操作
    • 求子串: bool SubString(SString &Sub,SString S, int pos, int len)
    • 串的比较:int StrCompare(SString S, SString T)
    • 求串在主串中的位置:int Index(sString S, SString T)
• 串的模式匹配
  • 朴素模式匹配算法
    • 原理：暴力破解
    • 算法思想
      • 主串长度n,模式串长度m
      • 将主串中所有长度为m的子串与模式串比对
      • 找到第一个与模式串匹配的子串，并返回子串起始位置
      • 若所有子串都不匹配，则返回0
    • 最坏时间复杂度=O(nm)
  • KMP算法
    • 不匹配的字符之前，一定是和模式串一致的
    • 依赖于模式串，与主串没有关系
    • 主要优点：主串指针不回溯
    • 用一个next数组存储模式串指针
    • 算法思想
      • 根据模式串T，求出next数组
      • 利用next数组进行匹配（主串指针不回溯）
      • 对于每模式串 t 的每个元素 t j，都存在一个实数 k ，使得模式串 t 开头的 k 个字符（t 0 t 1…t k-1）依次与 t j 前面的 k（t j-k t j-k+1…t j-1，这里第一个字符 t j-k 最多从 t 1 开始，所以 k < j）个字符相同。如果这样的 k 有多个，则取最大的一个。模式串 t 中每个位置 j 的字符都有这种信息，采用 next 数组表示，即 next[ j ]=MAX{ k }
    • 求next数组
      • next数组的作用：当模式串的第j个字符失配时，从模式串的第next[j]的继续向后匹配
      • next[1]无脑写0
      • next[2]无脑写1
      • 其他next：在不匹配的位置前，划一根美丽的分界线
    • 最坏时间复杂度=O(m+n)
    • KMP算法的优化
      • 求nextval数组
        • 先求next数组
        • 若next数组所对应位置的字符和当前字符相等，将对应位置的next数组赋值到当前位置的nextval数组
  • 子主题3