串的定义和实现

串($string$)是由零个或多个字符组成的有限序列。一般记为$S=`a_1a_2...a_n`~~(n\geq0)$。$S$是串名，单引号括起来的字符序列是串的值；$a_i$可以是字母、数字或其他字符；串中字符的个数$n$称为串的长度。$n=0$时的串称为空串(用$\empty$表示)。

串中任意多个连续的字符组成的子序列称为该串的子串，包含子串的串称为主串。

某个字符在串中的序号称为该字符在串中的位置。子串在主串中的位置以子串的第一个字符在主串中的位置来表示。当两个串的长度相等且每个对应位置的字符都相等时，称这两个串是相等的。

串的逻辑结构和线性表极为相似，区别仅在于串的数据对象限定为字符集。串的基本操作：

• $StrAssign~(\&T,chars)$：赋值操作。把串$T$赋值为$chars$。
• $StrCompare~(S,T)$：比较操作。若$S>T$，则返回值$>0$；若$S=T$，则返回值$=0$；若$S<T$，则返回值$<0$。
• $StrLength~(S)$：求串长。返回串$S$的元素个数。
• $Concat~(\&T,S1,S2)$：串联接。用$T$返回由$S1$和$S2$联接而成的新串。
• $Substring~(\&Sub,S,pos,len)$：求子串。用$Sub$返回串$S$的第$pos$个字符起长度为$len$的子串。
• $StrCopy~(\&T,S)$：复制操作。由串$S$复制得到串$T$。
• $StrEmpty~(S)$：判空操作。若$S$为空串，则返回$TRUE$，否则返回$FALSE$。
• $Index~(S,T)$：定位操作。若主串$S$中存在与串$T$值相同的子串，则返回它在主串$S$中第一次出现的位置；否则函数值为$0$。
• $ClearString~(\&S)$：清空操作。将$S$清为空串。
• $DestroyString~(\&S)$：销毁串。将串$S$销毁。

字符集编码：任何数据存到计算机中一定是二进制数。要确定一个字符和二进制数的对应规则，这就是“编码”。“字符集”：英文字符―—$ASCII$字符集；中英文―—$Unicode$字符集，基于同一个字符集，可以有多种编码方案，如:UTF-8，UTF-16。采用不同的编码方式，每个字符所占空间不同，考研中只需默认每个字符占$1B$即可。

串的存储结构有三种：

• 定长顺序存储表示(静态数组实现)：类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。在串的定长顺序存储结构中，为每个串变量分配一个固定长度的存储区，即定长数组。

  #define MAXLEN 255        // 预定义最大串长
  typedef struct{
      char ch[MAXLEN];    // 每个分量存储一个字符
      int length;            // 串的实际长度，只能小于等于 MAXLEN，超过部分被截断
  }SString;
  

  串长的表示方法：

  • 用一个额外的变量$length$来存放串的长度。
  • 在串值后面加一个不计入串长的结束标记字符"\0"(对应$ASCII$码的$0$)，此时的串长为隐含值。
  • 用$ch[0]$充当$length$，优点：字符的位序和数组下标相同，但是字长最大为$255$。
  • $ch[0]$废弃不用，用一个额外的变量$length$来存放串的长度。(教材使用的方法)

• 堆分配存储表示(动态数组实现)：以一组地址连续的存储单元存放串值的字符序列，但它们的存储空间是在程序执行过程中动态分配得到的。

  typedef struct{
      char *ch;        // 按串长分配存储区，ch 指向串的基地址
      int length;        // 串的长度
  }HString;
  

  在$C$语言中，存在一个称之为“堆"的自由存储区，并用$malloc()$和$free()$函数来完成动态存储管理。利用$malloc()$为每个新产生的串分配一块实际串长所需的存储空间，若分配成功，则返回一个指向起始地址的指针，作为串的基地址，这个串由$ch$指针来指示；若分配失败，则返回$NULL$。已分配的空间可用$free()$释放掉。

• 块链存储表示：类似于线性表的链式存储结构，也可采用链表方式存储串值。每个结点既可以存放一个字符，也可以存放多个字符。每个结点称为块，整个链表称为块链结构。最后一个结点占不满时通常用"#"补上。

  typedef struct StringNode{
      char ch[4];                    // 每个结点存多个字符
      struct StringNode *next;    // 指向下一个结点
  }StringNode, *String;
  

串的模式匹配

子串的定位操作通常称为串的模式匹配，它求的是子串在主串中的位置。这里采用定长顺序存储结构。(子串是主串的一部分，一定存在于主串，模式串不一定能在主串中找到)

朴素模式匹配算法：不依赖于其他串操作的暴力匹配算法。算法思想为：从主串$S$的第一个字符起，与模式$T$的第一个字符比较，若相等，则继续逐个比较后续字符；否则从主串的下一个字符起，重新和模式的字符比较；以此类推，直至模式$T$中的每个字符依次和主串$S$中的一个连续的字符序列相等，则称匹配成功，函数值为与模式$T$中第一个字符相等的字符在主串$S$中的序号，否则称匹配不成功，函数值为零。

最坏时间复杂度为$O(nm)$，其中$n$和$m$分别为主串和模式串的长度。

int Index(SString S,SString T){
    int i=1,j=1;
    while(i<=S.length && j<=T.length){
        if(S.ch[i]==T.ch[j]){
            ++i,++j;                    // 继续比较后继字符
        }else{
            i=i-j+2;                    // 指针后退重新开始匹配
            j=1;
        }
    }
    if(j>T.length)return i-T.length;    
    else return 0;
}

KMP算法：如果已匹配相等的前缀序列中有某个后缀正好是模式的前缀，那么就可以将模式向后滑动到与这些相等字符对齐的位置，主串$i$指针无须回溯(即$i$不变)，并从该位置开始继续比较($j$变为该值)。而模式向后滑动位数的计算仅与模式本身的结构有关，与主串无关。$KMP$算法可以在$O(n+m)$的时间数量级上完成串的模式匹配操作。其中，求$next$数组时间复杂度$O(m)$，模式匹配过程最坏时间复杂度$O(n)$。

前缀指除最后一个字符以外，字符串的所有头部子串；

后缀指除第一个字符外，字符串的所有尾部子串；

部分匹配值则为字符串的前缀和后缀的最长相等前后缀的字符串长度。

以'$ababa$'为例进行说明，求$next$数组：(一般掌握手动求数组即可，很少考代码实现)

• '$a$'的前缀和后缀都为空集，最长相等前后缀长度为$0$。

• '$ab$'的前缀为$\{a\}$，后缀为$\{b\}$，最长相等前后缀长度为$0$。

• '$aba$'的前缀为$\{a,ab\}$，后缀为$\{a,ba\}$，最长相等前后缀长度为$1$。

• '$abab$'的前缀为$\{a,ab,aba\}$，后缀为$\{b,ab,bab\}$，最长相等前后缀长度为$2$。

• '$ababa$'的前缀为$\{a,ab,aba,abab\}$，后缀为$\{a,ba,aba,baba\}$，最长相等前后缀长度为$3$。

• 得到部分匹配值$PM$表：

  编号	$1$	$2$	$3$	$4$	$5$
  $S$	$a$	$b$	$a$	$b$	$a$
  $PM$	$0$	$0$	$1$	$2$	$3$

  将$PM$表右移一位，得到$next$数组，第一个数用$-1$填充：(为了算法方便，将$next$的值均加一)

  编号	$1$	$2$	$3$	$4$	$5$
  $S$	$a$	$b$	$a$	$b$	$a$
  $next$	$-1$	$0$	$0$	$1$	$2$
  $next+1$	$0$	$1$	$1$	$2$	$3$

  $next[1]$都写$0$，$next[2]$都写$1$。

  void get_next(SString T,int next[]){    // 求 next 数组
      int i=1,j=0;
      next[1]=0;
      while(i<T.length){
          if(j==0 || T.ch[i]==T.ch[j]){
              ++i;++j;
              next[i]=j;
          }else{
              j=next[j];
          }
      }
  }
  

当$next$指向的字符与当前编号的字符相同时，需要改为$next$指向的字符的$next$值，直到$next$指向的字符不一致或为第一次出现的字符，改进后的算法手算方法为：先求$next$数组，再由$next$数组求$nextval$数组。

代码如下：

void get_nextval(SString T,int nextval[]){    // 求 next 数组优化后的 nextval 数组
    int i=1,j=0;
    nextval[1]=0;
    while(i<T.length){
        if(j==0 || T.ch[i]==T.ch[j]){
            ++i;++j;
            if(T.ch[i]!=T.ch[j])nextval[i]=j;
            else nextval[i]=nextval[j];
        }else{
            j=nextval[j];
        }
    }
}

算法步骤：

1. 比较主串元素$S[i]$和子串元素$T[j]$是否相等。
2. 若相等$i,j$均加一；若不等，将$j$的值修改为对应编号的$next$值(括号中加一后的值)，若$next$的值为$0$，则将$i$的值加一，$j$的值变为$1$。
3. 若$j$的值大于子串的长度，则匹配成功。
4. 否则继续步骤$1$，直到主串匹配到末尾或匹配成功。

int Index_KMP(SString S,SString T,int next[]){    // 字符串数组的第0位舍弃
    int i=1,j=1;
    while(i<=S.length && j<=T.length){
        if(j==0 || S.ch[i]==T.ch[j]){
            ++i,++j;                    // 继续比较后继字符
        }else{
            j=next[j];                    // 模式串向右移动
        }
    }
    if(j>T.length)return i-T.length;    // 匹配成功
    else return 0;
}