52. 串

发表于 更新于 分类于

串的定义

  1. 定义：由零个或多个字符组成的有限序列，又名叫字符串
  2. 所谓的序列，说明串的相邻字符之间具有前驱和后继的关系
  3. 子串在主串中的位置就是子串的第一个字符在主串种的序号

串的比较

  1. 串的比较是通过组成串的字符之间的编码来进行的
  2. 字符的编码指的是字符再对应字符集中的序号
  3. 类似于：查字典就是在比较字符串大小的过程

串的抽象数据类型

  1. 字符串与线性表的差别：
    1. 线性表更关注的是单个元素的操作，比如查找一个元素，插入或删除一个元素
    2. 串中更多的是查找子串的位置、得到指定位置子串、替换子串等操作

朴素的模式匹配算法

  1. 子串的定位操作通常称作串的模式匹配
  2. 简单的说，就是对主串的每一个字符作为子串开头，与要匹配的字符串进行匹配。对主串做大循环，每个字符开头做T长度的小循环，指导匹配成功或全部遍历完成为止。
  3. S的长度放在S[0]中，T的长度放在T[0]中
  4. 代码 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    int Index(string S, string T, int pos) 
    {
          int i = pos;
          int j = 1;
          while (i <= S[0] && j <= T[0]) {
             if (S[i] == T[j]) {
                   i++;
                   j++;
             }
             else {
                   i = i - j + 2;
                   j = 1;
             }

          }
          if (j > T[0]) return i - T[0];
          else return 0;
    }

KMP模式匹配算法