王道

串

知识框架

基本概念:主串、子串、串长
存储结构
- 定长顺序存储
- 堆分配存储
- 块链存储
模式匹配算法
- 暴力匹配法
- KMP算法
  - 部分匹配值表
  - next数组
  - next函数的推理过程
- KMP算法的进一步改进——nextval数组

串的实现和定义

串的定义

串(string）是由零个或多个字符组成的有限序列。一般记为

$S='a_1a_2\cdots a_n' \quad (n \geq 0)$

其中，$S$是串名，单引号括起来的字符序列是串的值;$a_i$可以是字母、数字或其他字符;串中字符的个数n称为串的长度。$n=0$时的串称为空串（用$\emptyset$表示)。

串中任意多个连续的字符组成的子序列称为该串的$\color{green}{\text{子串}}$，相应地，包含子串的串称为$\color{green}{\text{主串}}$。某个字符在串中的序号称为该字符在串中的位置。子串在主串中的位置以子串的第一个字符在主串中的位置来表示。当两个串的长度相等且每个对应位置的字符都相等时，称这两个串是相等的。

例如，有串A=’China Beijing’，B= ‘Beijing’，C=’China’，则它们的长度分别为13,7和5。B和C是A的子串，B在A中的位置是7，C在A中的位置是1。

需要注意的是，由一个或多个空格（空格是特殊字符）组成的串称为$\color{green}{\text{空格串}}$(注意，空格串不是空串)，其长度为串中空格字符的个数。

串的逻辑结构和线性表极为相似，区别仅在于串的数据对象限定为$\color{green}{\text{字符集}}$。在基本操作上，串和线性表有很大差别。线性表的基本操作主要以单个元素作为操作对象，如查找、插入或删除某个元素等;而串的基本操作通常以子串作为操作对象，如查找、插入或删除一个子串等。

串的存储结构

定长顺序存储表示

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

#define MAXLEN 255//预定义最大串长为255
typedef struct {
char ch [MAXLEN] ;//每个分量存储一个字符
int length;//串的实际长度
}SString;

串的实际长度只能小于等于MAXLEN，超过预定义长度的串值会被舍去，称为$\color{green}{\text{截断}}$。串长有两种表示方法:一是如上述定义描述的那样，用一个额外的变量len来存放串的长度;二是在串值后面加一个不计入串长的结束标记字符“\0”，此时的串长为隐含值。

在一些串的操作（如插入、联接等）中，若串值序列的长度超过上界MAXLEN，约定用“截断”法处理，要克服这种弊端，只能不限定串长的最大长度，即采用动态分配的方式。

堆分配存储表示

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

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

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

块链存储表示

类似于线性表的链式存储结构，也可采用链表方式存储串值。由于串的特殊性（每个元素只有一个字符)，在具体实现时，每个结点既可以存放一个字符，也可以存放多个字符。每个结点称为块，整个链表称为块链结构。图4.1(a)是结点大小为4(即每个结点存放4个字符）的链表，最后一个结点占不满时通常用“#”补上;图4.1(b)是结点大小为1的链表。

串的基本操作

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

不同的高级语言对串的基本操作集可以有不同的定义方法。在上述定义的操作中，串赋值StrAssign、串比较StrCompare、求串长StrLength、串联接Concat 及求子串SubString五种操作构成串类型的最小操作子集，即这些操作不可能利用其他串操作来实现;反之，其他串操作（除串清除clearstring和串销毁Destroystring外)均可在该最小操作子集上实现。
例如，可利用判等、求串长和求子串等操作实现定位函数Index(S,T)。算法思想为:在主串S中取从第一个字符起、长度和串T相等的子串，与串T比较，若相等则求得函数值为i，否则i值增1，直至串S中不存在和串T相等的子串为止。

int Index(String S,String T){
  int i=1,n=StrLength(s), m=StrLength (T);
  while(i<-n-m+1){
    SubString(sub, s,i, m);
    if (StrCompare (sub, T)!=0)++i;
    else return i;//返回子串在主串中的位置
  }
  return 0; //S中不存在与T相等的子串
}

串的模式匹配

简单的模式匹配算法

子串的定位操作通常称为串的模式匹配，它求的是子串（常称$\color{green}{\text{模式串}}$）在主串中的位置。这里采用定长顺序存储结构，给出一种不依赖于其他串操作的暴力匹配算法。

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;
}

图4.2展示了模式T= ‘ abcac’和主串s的匹配过程，每次匹配失败后，都把模式T后移一位。

改进的模式匹配算法——KMP算法

图4.2的匹配过程,在第三趟匹配中，i=7、j=5的字符比较不等，于是又从i=4、j=1重新开始比较。然而，仔细观察会发现，i=4和j=1，i=5和i=1及i=6和j=1这三次比较都是不必进行的。从第三趟部分匹配的结果可知，主串中第4、5和6个字符是’b’、’c’和’a’(即模式中第2、3和4个字符)，因为模式中第一个字符是’ a ‘，因此它无须再和这3个字符进行比较，而仅需将模式向右滑动3个字符的位置，继续进行i=7、j=2时的比较即可。

在暴力匹配中，每趟匹配失败都是模式后移一位再从头开始比较。而某趟已匹配相等的字符序列是模式的某个前缀，这种频繁的重复比较相当于模式串在不断地进行自我比较，这就是其低效率的根源。因此，可以从分析模式本身的结构着手，如果已匹配相等的前缀序列中有某个后缀正好是模式的前缀，那么就可以将模式向后滑动到与这些相等字符对齐的位置，主串i指针无须回溯，并从该位置开始继续比较。而模式向后滑动位数的计算仅与模式本身的结构有关，与主串无关（这里理解起来会比较困难，没关系，带着这个问题继续往后看)。