data structure

字符串简称串,计算机上非数值处理的对象基本都是字符串数据。我们常见的信息检索系统(如搜索引擎)、文本编辑次序(如 word)、问答系统、自然语言翻译系统等,都是以字符串数据作为处理对象的。本章详细介绍字符串的存储结构及相应的操作。

1. 串的定义

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

S = 'a1a2...an' (n0)

其中,S 是串名,单引号括起来的字符序列是串的值;ai 可以是字母、数字或其他字符;串中字符的个数 n 称为串的长度。n=0 时的串称为空串。

串中任意个连续的字符组成的子序列称为该串的子串,包含子串的串相应地称为主串。通常称字符在序列中的序号为该字符在串中的位置。子串在主串中的位置以子串的第一个字符在主串中的位置来表示。当两个串的长度相等且每个对应位置的字符都相等时,称这两个串是相等的 。

需要注意的是,由一个或多个空格(空格是特殊字符)组成的串称为空格串(注意,空格串不是空串),其长度为串中空格字符的个数。

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

2. 串的存储结构

2.1 定长顺序存储表示

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

#define MAXLEN 255  // 预定义最大串为 255

struct SString {
    char ch[MAXLEN];  // 每个分量存储一个字符
    int length;       // 串的实际长度
};

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

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

2.2 堆分配存储表示

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

struct HString {
    char *ch;     // 按串长分配存储区
    int lenght;   // 串的长度
};

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

上述两种存储表示通常为高级程序设计语言所采用。块链存储表示仅做简单介绍。

2.3 块链存储表示

类似于线性表的链式存储结构,也可采用链表方式存储串值。由于串的特殊性(每个元素只有一个字符),在具体实现时,每个结点既可用存放一个字符,又可以存放多个字符。每个结点称为块,整个链表称为块链结构。

3. 串的基本操作

对于串的基本操作集,不同的高级程序设计语言可以有不同的定义方法。在上述定义的操作中,串赋值 StrAssign 、串比较 StrCompare 、求串长 StrLength 、串联接 Concat 及求子串 SubString 五种操作构成串类似的最小操作子集 ,即这些操作不可能利用其他串操作来实现;反之,其他串操作(除串清除 ClearString 和串销毁 DestroyString 外)均可在这个最小操作子集上实现 。

4. 串的模式匹配

子串的定位操作通常称为串的模式匹配,它求的是子串(常称模式串)在主串的位置。上节中曾利用串的其他基本操作给出了定位操作的一种算法,这里采用定长顺序存储结构,写出一种不依赖于其他串操作的匹配算法。

int Index() ... 未完待续

在上述算法中,分别用计数指针 i 和 j 指示主串 S 和模式串 T 中当前正待比较的字符位置。算法思想为:从主串 S 的第 pos 个字符起,与模式的第一个字符比较,若相等,则继续逐个比较后序字符;否则从主串的下一个字符起,重新和模式的字符比较;以此类推,直至模式 T 中的每个字符依次和主串 S 中的一个连续的字符序列相等,则称匹配成功,函数值为与模式 T 中第一个字符相等的字符在主串 S 中的序号,否则称匹配不成功,函数值为零。

简单模式匹配算法的最坏时间复杂度为 O(nm) ,其中 n 和 m 分别为主串和模式串的长度。

5. 改进的模式匹配算法(KMP 算法)

KMP 算法利用比较过的信息,i 指针不需要回溯,仅将子串向后滑动一个合适的位置,并从这个位置开始和主串进行比较,这个合适的位置仅与子串本身的结构有关,而与主串无关。

5.1 字符串的前缀、后缀和部分匹配值

要了解子串的结构,首先要弄清楚几个概念:前缀、后缀和部分匹配值。前缀指除了最后一个字符以外,字符串的所有头部子串;后缀指除了第一个字符外,字符串的所有尾部子串;部分匹配值则为字符串的前缀和后缀的最长相等前后缀长度。下面以 ababa 为例进行说明:

故字符串 ababa 的部分匹配值为 00123 。

这个部分匹配值有什么作用呢?

回到最初的问题。主串为 ababcabcacbab ,子串为 abcac

利用上述方法容易写出子串 abcac 的部分匹配值为 00010 ,将部分匹配值写出数组形式,就得到了 next 数组。

  1. 第一趟匹配过程

    发现 c 和 a 不匹配,前面的两个字符 ab 是匹配的,查表可知,最后一个匹配字符 b 对应的部分匹配值为 0,因此按照下面的公式计算出子串需要向后移动的位数:

    移动位数=已匹配的字符数-对应的部分匹配值

    因为 2-0=2,所以将子串向后移动两位然后进行第二趟匹配

  2. 第二趟匹配

    发现 c 与 b 不匹配,前面 4 个字符 abca 是匹配的,最后一个匹配字符 a 对应的部分匹配值为 1,4-1=3,将子串向后移动 3 位,进行第三趟匹配。

  3. 第三趟匹配过程

    子串全部比较完成,匹配成功。

可以发现,整个匹配过程中,主串始终没有回退,故 KMP 算法可以在 O(n+m) 的时间数量级上完成串的模式匹配操作,大大提高了匹配效率 。

5.2 KMP 算法的原理

最长相等前后缀就是 KMP 算法的精髓,简单的理解就是移动一定的位数使得重叠部分对应字符相同,所以我们可以得到 移动位数=已匹配的字符数-对应的部分匹配值 。写出算法形式为

move = j - next[j-1]

这里的索引 j 是从 0 开始的,后面的索引都是从 0 开始。使用部分匹配值时,每当匹配失败,就去找它前一个元素的部分匹配值,这样使用起来不方便,所以将 next 数组右移一位,这样哪个元素匹配失败,直接看它子集的部分匹配值即可。

此时,应该注意到:

  1. 第一个元素右移以后空缺的用 -1 来填充,因为若是第一个元素匹配失败,则需要将主串向右移动,则不需要计算子串移动的位数。
  2. 最后一个元素在右移的过程中溢出,因为原来的子串中,最后一个元素的部分匹配值是其下一个元素使用的,但显然已没有下一个元素,故可以舍去。

这样,上式就改写为

move = j - next[j]

第 j 个字符匹配失败后,j 得往前移动 move 个单位(也就是子串回溯),重新开始匹配,得到字符串移动公式:

j=j-move=j-(j-next[j])=next[j]

即每次将子串回溯到 next[j] 的位置和主串继续比较 。

对人而言,用上述方法很容易求出 next 数组,但对于计算机来说,可以用一种更加高效的方式来求 next 数组。

设 T 为子串,当 next[j] 已经求得,next[j+1] 的值可以分两种情况来分析。

  1. 若子串中字符 tj 等于 ti,显然 next[i+1]=j+1 ,因为 j 为当前 T 最长相等前后缀长度。
  2. tj 不等于 ti ,将 t(i-j) ... ti 当作主串,将 t0...tj 当作子串。类似于失配问题,需移动子串,即令 j=next[j] ,继续比较,若满足 1,则求得 next[j+1]

提示 :next[i] 求的是 t0~t(i-1) 的最长相等前后缀长度。

综合上述得到伪代码如下:

void get_next(string T, int next[]) {
    
}

计算机执行起来效率很高,但对于我们手工计算来说会很难。因此,当我们需要手工计算的时候,依然还是使用最初的方法。

与 next 数组的求解比较,KMP 的匹配算法相对要简单很多,它在形式上与简单的模式匹配算法很相似。不同之处仅在于当匹配过程产生失配时,指针 i 不变,指针 j 退回到 next[j] 的位置并重新开始进行比较,并且当指针 j 为 0 时,指针 i 和 j 同时加 1。即若主串的第 i 个位置和模式串的的第一个字符不等,则应从主串的第 i+1 个位置开始匹配。伪代码如下:

int Index_KMP(string S, string T, int next[], int pos) {
    
}

尽管普通模式匹配的时间复杂度是 O(nm) ,KMP 算法的时间复杂度是 O(m+n) ,但在一般情况下,普通模式匹配的执行时间近似为 O(m+n) ,因此至今仍被采用。KMP 算法仅在主串与子串有很多 “部分匹配” 时才显得比普通算法快很多,其主要优点是主串不回溯。