数据结构：字符串

抱抱宝

5601人浏览 · 2023-03-21 00:22:54

抱抱宝 · 2023-03-21 00:22:54 发布

1.字符串

字符串∶简称为串，是由零个或多个字符组成的有限序列。一般记为 $\text{[math]}$ 。

字符串的长度︰字符串中字符的数目n称为字符串的长度。

空串:零个字符构成的串也称为「空字符串」，它的长度为0，可以表示为" "。

子串∶字符串中任意个连续的字符组成的子序列称为该字符串的「子串」。并且有两种特殊子串，起始于位置为0、长度为k的子串称为「前缀」。而终止于位置n -1、长度为k的子串称为「后缀」。

主串:包含子串的字符串相应的称为「主串」。

举个例子：

str="Hello world"

在示例代码中，str是一个字符串的变量名称，Hello World则是该字符串的值，字符串的长度为11。该字符串的表示如下图所示∶

2.字符串的比较

2.1字符串的比较操作

字符串之间的大小取决于它们按顺序排列字符的前后顺序。比如字符串 str1 = "abc" 和 str2 = "acc"，

它们的第一个字母都是 a，而第二个字母，由于字母 b 比字母 c 要靠前，所以 b < c，于是我们可以

说 "abc" < "acd" ，也可以说 str1 < str2。

字符串之间的比较是通过组成字符串的字符之间的「字符编码」来决定的。而字符编码指的是字符在对

应字符集中的序号。

对于两个不相等的字符串，我们可以以下面的规则定义两个字符串的大小：

从两个字符串的第 0 个位置开始，依次比较对应位置上的字符编码大小。

如果 str1[i] 对应的字符编码等于 str2[i] 对应的字符编码，则比较下一位字符。

如果 str1[i] 对应的字符编码小于 str2[i] 对应的字符编码，则说明 str1 < str2。比如："abc" <

"acc"。

如果 str1[i] 对应的字符编码大于 str2[i] 对应的字符编码，则说明 str1 > str2。比如："bcd" >

"bad"。

如果比较到某一个字符串末尾，另一个字符串仍有剩余：

如果字符串 str1 的长度小于字符串 str2，即 len(str1) < len(str2)。则 str1 < str2。比如："abc" < "abcde"。

如果字符串 str1 的长度大于字符串 str2，即 len(str1) > len(str2)。则 str1 > str2。比如："abcde" > "abc"。

如果两个字符串每一个位置上的字符对应的字符编码都相等，且长度相同，则说明 str1 == str2，比如："abcd" == "abcd"。

按照上面的规则，我们可以定义一个 strcmp 方法，并且规定：

当 str1 < str2 时，strcmp 方法返回 -1。

当 str1 == str2 时，strcmp 方法返回 0。

当 str1 > str2 时，strcmp 方法返回 1。

2.2字符串比较代码

def strcmp (str1, str2):
    index1, index2 = 0,0
    while index1< len(str1 ) and index2< len(str2):
        if ord(str1 [index1] )== ord(str2 [ index2 ]):
            index1 += 1
            index2 += 1
    elif ord(str1[ index1])< ord(str2 [index2]):
        return -1
    else:
        return 1

    if len (str1)< len(str2) :
        return-1
    elif len(str1)> len (str2):
        return 1
    else:
        return 0

2.3字符串的字符编码

以计算机中常用字符使用的 ASCII 编码为例。最早的时候，人们制定了一个包含 127 个字符的编码表

ASCII 到计算机系统中。ASCII 编码表中的字符包含了大小写的英文字母、数字和一些符号。每个字符

对应一个编码，比如大写字母 A 的编码是 65，小写字母 a 的编码是 97。后来又针对特殊字符，将

ASCII 扩展到了 256 位。

ASCII 编码可以解决以英语为主的语言，可是无法满足中文编码。为了解决中文编码，我国制定了

GB2312、GBK、GB18030 等中文编码标准，将中文编译进去。但是世界上有上百种语言和文字，各

国有各国的标准，就会不可避免的产生冲突，于是就有了 Unicode 编码。Unicode 编码最常用的就

是 UTF-8 编码，UTF-8 编码把一个 Unicode 字符根据不同的数字大小编码成 1 ~ 6 个字节，常用的

英文字母被编码成 1 个字节，汉字通常是 3 个字节。

2.4字符串的存储结构

字符串的存储结构跟线性表相同，分为「顺序存储结构」和「链式存储结构」。

3.字符串匹配问题

字符串匹配：又称「模式匹配」。可以简单理解为，给定字符串 T 和 p，在主串 T 中寻找子串 p。主

串 T 又被称为「文本串」，子串 p 又被称为「模式串」。

在字符串问题中，最重要的问题之一就是字符串匹配问题。而按照模式串的个数，我们可以将字符串匹

配问题分为：「单模式串匹配问题」和「多模式串匹配问题」。

3.1单模式串匹配问题

单模式匹配问题︰给定一个文本串T = tt2….tn，再给定一个特定模式串p = PPp2..pn。要求从文本串T找出特定模式串p的所有出现位置。

根据在文本中搜索模式串方式的不同，可以将单模式匹配算法分为以下三种:

基于前缀搜索方法∶在搜索窗口内从前向后（沿着文本的正向）逐个读入文本字符，搜索窗口中文本和模式串的最长公共前缀。著名的KMP算法和更快的 Shift-Or算法使用的就是这种方法。

基于后缀搜索方法：在搜索窗口内从后向前（沿着文本的反向）逐个读入文本字符，搜索窗口中文本和模式串的最长公共后缀。使用这种搜索算法可以跳过一些文本字符，从而具有亚线性的平均时间复杂度。最著名的 BM 算法，以及 Horspool 算法、Sunday 算法都使用了这种方法。

基于子串搜索方法：在搜索窗口内从后向前（沿着文本的反向）逐个读入文本字符，搜索满足「既是窗口中文本的后缀，也是模式串的子串」的最长字符串。与后缀搜索方法一样，使用这种搜索方法也具有亚线性的平均时间复杂度。这种方法的主要缺点在于需要识别模式串的所有子串，这是一个非常复杂的问题。Rabin-Karp 算法、BDM 算法、BNDM 算法和 BOM 算法使用的就是这种思想。其中，Rabin-Karp 算法使用了基于散列的子串搜索算法。

3.2多模式串匹配问题

多模式匹配问题∶给定一个文本串 $\text{[math]}$ ，再给定一组模式串 $\text{[math]}$ ，其中每个模式串 $\text{[math]}$ 是定义在有限字母表上的字符串 $\text{[math]}$ 。要求从文本串T中找到模式串集合Р中所有模式串 $\text{[math]}$ 的所有出现位置。