52. 串

• 串的定义

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

• 串的比较

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

• 串的抽象数据类型

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

• 朴素的模式匹配算法

  1. 子串的定位操作通常称作串的模式匹配
  2. 简单的说，就是对主串的每一个字符作为子串开头，与要匹配的字符串进行匹配。对主串做大循环，每个字符开头做T长度的小循环，指导匹配成功或全部遍历完成为止。
  3. S的长度放在S[0]中，T的长度放在T[0]中
  4. 代码

     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模式匹配算法