④串

24自用408数据结构，串是由零个或多个字符组成的有限序列，字符可以是零、字符也可以是空格，通常以子串作为操作对象。

串

• 串的定义
  • 串是由零个或多个字符组成的有限序列
    • 注意
      • 字符可以是零
      • 字符也可以是空格
  • 主串包含子串
    • 通常以子串作为操作对象
  • 串相等的条件
    • 长度相同
    • 每个位置对应字符相同
• 串的存储结构
  • 定长顺序存储
    • 用一组地址连续的存储单元存储串值的字符序列。为每个串变量分配一个固定长度的存储区，即定长数组
    • 截断
      • 将超过预定义长度的串值会被舍去
    • 串长表示方法
      • 用一个额外变量len来记录串长
      • 在串值后面加一个不记入串长的结束标记字符\0，此时串长为隐含值
  • 堆分配存储
    • 依然用一组地址连续的存储单元存放串值的字符序列，但存储空间是执行过程中动态分配的
    • 使用malloc()和free()函数来完成在堆(自由存储区)的动态存储管理
  • 块链存储
    • 类似线性表的链式存储。每个结点称为块(每个结点可以存放1个字符，也可以多个字符，即块大小不一)
    • 存储密度小
    • 存不满时可用'#'表示
• 串的模式匹配
  • 简单的模式匹配算法
    • 暴力解法
      • 从主串的头开始依次比较每个字符，不同时，回溯至i-j+2处
    • 主串长：m 模式串：n
      • 最多有n-m+1个字串
    • 最坏时间复杂度为O(n(n-m+1))，即O(nm)
    • 主串指针需要回溯
  • KMP算法
    • 部分匹配值步骤
      • 1| 从字符1开始找到最长相等前后缀
      • 2| 最后罗列出来即可
      • 3| 例：ababa的部分匹配值为00123
    • 得到next数组步骤
      • 1| 部分匹配值
        • 子串逻辑右移位数＝已匹配字符数 - 对应的部分匹配值 Move＝(j-1)-PM[j-1]
      • 2| 右移匹配值
        • 子串指针变化公式：j＝next[j]+1
      • 3| 匹配值+1
        • 得到next数组
          • 子串指针变化公式：j＝next[j]
      • 手算求next数组，第j个元素的next数组的值为前j-1个元素的最长相等前后缀长度+1
    • 当子串和模式不匹配时，主串指针i不回溯，模式串指针j＝next[j]
    • 时间复杂度：O(m+n)
  • KMP优化
    • nextval数组
      • 将next[next[i]]的值与i比较，若相等，则把next[i]的值改为nextval[next[i]]的值；否则不改变，即nextval[i]＝next[i]
        • 手算求nextval数组
          • Pj ≠ Pnext[j]
            • Pnextval[j]＝next[j]
          • Pj ＝ Pnext[j]
            • Pnextval[j]＝Pnextval[Pnext[j]]
      • 例如 ababaaababaa的nextval数组为010104210104
• 第一个字符匹配失败，整个字符串右移 所以next数组第一个字符为0(从1开始) 或-1(从0开始)