数据结构：字符串

在计算机系统中，非数值对象大部分是字符串数据。然而，现今所使用的计算机硬件结构是面向数值计算的需要而设计的，因此，在处理字符串数据时要比处理整数和浮点数复杂得多。想要有效地处理字符串数据，就必须对字符串这个数据结构有深入的了解。

一、串的定义

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

$$s=“a_1a_2...a_n” (n>=0)$$

其中，s是串的名字，用双引号括起来的字符序列是串的值；$a_i$(1<=i<=n)可以是字母、数字或其他字符；串中字符的个数n称为串的长度。零个字符的串称为空串（null string），其长度为零。

串中任意个连续的字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。通常称字符在序列中的序号为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。例如，假设有如下4个串：

a="BEI";
b="JING";
c="BEIJING";
d="BEI JING";

它们的长度分别为3、4、7和8；并且a和b都是c和d的子串，a在c和d中的位置都是1，而b在c中的位置是4，在d中的位置则是5。

当两个串的值相等时，就称这两个串是相等的。这里的相等，指的是两个串的长度相等，并且各个位置上的字符都相等。例如，上例中的串a、b、c和d彼此都不相等。

一般情况下，空格也是串中的一个元素，可以出现在其他字符中间。由一个或多个空格（“ ”）组成的串称为空格串（blank string），其长度为串中空格字符的个数。它不同于空串，为了清楚起见，通常用符号“Ø”来表示“空串”。

二、串的存储结构

与线性表类似，串也有两种存储结构：顺序存储和链式存储。但考虑到存储效率和算法的方便性，串多采用顺序存储结构。

2.1、顺序存储

串的顺序存储，是指用一组地址连续的存储单元存储串值的字符序列。按照预定义的大小，为每个串变量分配一个固定长度的存储区，则可用定长数组如下描述：

// 串的最大长度
#define MAXLEN 255

typedef struct {
    // 存储串值的一维数组
    char ch[MAXLEN+1];
    // 串的当前长度
    int length;
}SString;

其中，MAXLEN表示串的最大长度，ch是存储字符串的一维数组，每个分量存储一个字符，length表示字符串的当前长度。为了便于说明，在后续的算法描述当中，所用到的字符串的顺序存储都是从下标为1的数组分量开始存储的，下标为0的分量闲置不用。

上述定义方式是静态的，在编译时刻就确定了串空间的大小。而多数情况下，串的操作是以串的整体形式参与的，串变量之间的长度相差较大，在操作中字符串长度的变化也较大，这样为串变量设定固定大小的空间不尽合理。因此最好是根据实际需要，在程序执行过程中动态地分配和释放字符数组空间。

在C语言中，存在一个称之为“堆”（Heap）的自由存储区，可以用它为每个新产生的串动态分配一块实际串长所需的存储空间，若分配成功，则返回一个指向起始地址的指针，作为串的基址，同时为了以后处理方便，约定串长也作为存储结构的一部分。这种字符串的存储方式也称为串的堆式顺序存储结构，定义如下：

typedef struct {
    // 若是非空串，则按串长分配存储区，否则ch为NULL
    char *ch;
    // 串的当前长度
    int length;
}HString;

2.2、链式存储

我们知道，顺序存储结构的插入和删除操作不方便，需要移动大量的字符。因此，可采用单链表存储串。

由于串结构的特殊性——结构中的每个数据元素是一个字符，则在用链表存储串值时，存在一个“结点大小”的问题，即每个结点可以存放一个字符，也可以存放多个字符。例如，下图（a）所示的结点大小为4（即每个结点存放4个字符），下图（b）所示的结点大小为1。当结点大小大于1时，由于串长不一定是结点大小的整倍数，则链表中的最后一个结点不一定全被串值占满，此时通常补上“#”或其他的非串值字符（通常“#”不属于串的字符集，是一个特殊的符号）。

为了便于进行串的操作，当以链表存储串值时，除了设置头指针外，还可以附设一个尾指针指示链表中的最后一个结点，并给出当前串的长度。采用这种方式定义的串存储结构被称为块链结构，其定义如下：

#define CHUNKSIZE 80

typedef struct Chunk{
    char ch[CHUNKSIZE];
    struct Chunk *next;
}Chunk;

typedef struct {
    // 串的头、尾指针
    Chunk *head, *tail;
    // 串的当前长度
    int length;
}LString;

在链式存储方式中，结点大小的选择直接影响着串处理的效率。在各种串的处理系统中，所处理的串往往很长或很多，比如一本书的几百万个字符，情报资料的成千上万个条目，这就要求考虑串值的存储密度。显然，存储密度小（如结点大小为1时），运算处理方便，然而，存储占用量大。

如果在处理串的过程中，需进行内、外存交换的话，则会因为内、外存交换操作过多而影响处理的总效率。所以，串的字符集的大小也是一个重要因素。一般来说，字符集小，则字符的机内编码就短，这也影响串值存储方式的选取。

串值的链式存储结构对某些串操作，如联接操作等，有一定方便之处，但总地说来，不如顺序存储结构灵活，它占用存储量大且操作复杂。此外，采用链式存储结构时，串操作的实现和线性表在链表存储结构中的操作类似，故在此不作详细讨论。之后的模式匹配算法将采用串的定长顺序存储结构实现。

三、串的模式匹配算法

串的模式匹配，又称串匹配，它是一种子串定位运算。假设有两个字符串S和T，其中，S为主串，也称正文串；T为子串，也称为模式。在主串S中查找与模式T相匹配的子串，如果匹配成功，则返回相匹配的子串中的第一个字符在主串S中出现的位置。

串的模式匹配应用非常广泛。比如，在搜索引擎、拼写检查、语言翻译、数据压缩等应用中，都需要进行串匹配。著名的模式匹配算法有BF算法和KMP算法，接下来，我们将详细介绍这两种算法。

3.1、BF算法

BF算法中的BF是Brute Force的缩写，将它翻译成中文就是暴力匹配算法。

BF算法是最简单、最直观的模式匹配算法。其思想可以用一句话来概括，那就是：在主串中，检查起始位置分别是1、2、3、…、n-m+1，且长度为m的n-m+1个子串，看是否有跟模式串匹配的（注：这里的n为主串的长度，m为模式串的长度）。

如下图，展示了模式T=“abcac”和主串S=“ababcabcacbab”的匹配过程：

说明：

• 第1趟匹配，从主串的第1个字符开始比较，在主串的第3个字符处遇到不匹配，因此，进行第2趟匹配；
• 第2趟匹配，从主串的第2个字符开始比较，在主串的第2个字符处遇到不匹配，因此，进行第3趟匹配；
• 第3趟匹配，从主串的第3个字符开始比较，在主串的第7个字符处遇到不匹配，因此，进行第4趟匹配；
• 第4趟匹配，从主串的第4个字符开始比较，在主串的第4个字符处遇到不匹配，因此，进行第5趟匹配；
• 第5趟匹配，从主串的第5个字符开始比较，在主串的第5个字符处遇到不匹配，因此，进行第6趟匹配；
• 第6趟匹配，从主串的第6个字符开始比较，一直比较到模式串的末尾，也没遇到不匹配，因此匹配成功，返回。

3.1.1、算法描述

BF算法的实现步骤为：

• 分别利用计数指针i和j指示主串S和模式T中当前正待比较的字符位置，i初值为pos，j初值为1。（注：模式匹配不一定是从主串的第一个位置开始，可以在主串中指定查找的起始位置pos。）

• 如果两个串均未比较到串尾，即i和j均分别小于等于S和T的长度时，则循环执行以下操作：

  • 比较S.ch[i]和S.ch[j]，若相等，则i和j分别指示串中下一个位置，继续比较后续字符；
  • 若不等，则指针后退重新进行下一趟，即从主串的下一个字符（i=i-j+2）起再重新和模式的第一个字符（j=1）比较。

• 如果j>T.length，说明模式T中的每个字符依次和主串S中的一个连续的字符序列相等，则匹配成功，返回和模式T中第一个字符相等的字符在主串S中的序号（i-T.length）；否则称匹配不成功，返回0。

相应的算法描述为：

// 从主串S的第pos个字符开始，查找第一次出现模式T的位置。若不存在，则返回值为0
// 其中，T非空，1<=pos<=S.length
int Index_BF(SString S, SString T, int pos) {
    // i初始为pos，j初始为1
    i=pos; 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;
}

3.1.2、复杂度分析

BF算法的匹配过程易于理解，且在某些应用场合效率也较高。在匹配成功的情况下，考虑以下两种极端情况。

（1）最好情况下，每趟不成功的匹配都发生在模式串的第一个字符与主串中相应字符的比较。例如：

S="aaaaaba";
T="ba";

设主串的长度为n ，子串的长度为m ，假设从主串的第i 个位置开始与模式串匹配成功，则在前i −1趟匹配中字符总共比较了i −1次；第i 趟成功的字符比较次数为m ，则总比较次数为i −1+m 。对于成功匹配的主串，其起始位置的范围是1到n −m +1，假定这n −m +1个起始位置上的匹配成功概率相等，则最好的情况下匹配成功的平均比较次数为

$$\sum_{i=1}^{n-m+1} p_i(i-1+m) = \frac{1}{n-m+1}\sum_{i=1}^{n-m+1} i-1+m = \frac{1}{2} (n+m)$$

即最好情况下的平均时间复杂度是O(n+m)。

（2）最坏情况下，每趟不成功的匹配都发生在模式串的最后一个字符与主串中相应字符的比较。例如：

S="aaaaaab";
T="aab";

假设从主串的第i 个位置开始与模式串匹配成功，则在前i −1趟匹配中字符总共比较了(i −1) *m 次；第i 趟成功的字符比较次数为m ，则总比较次数i*m 。因此最坏情况下匹配成功的平均比较次数为

$$\sum_{i=1}^{n-m+1} p_i(i*m) = \frac{1}{n-m+1}\sum_{i=1}^{n-m+1} i*m = \frac{1}{2}m*(n-m+2)$$

即最坏情况下的平均时间复杂度是O(n*m)。

3.1.3、小结

BF算法思路直观简明。但当匹配失败时，主串的指针i 总是回溯到i-j+2位置，模式串的指针总是恢复到首字符位置j=1，因此，算法时间复杂度高。

尽管理论上，BF 算法的时间复杂度很高，是 O(n*m)，但在实际的开发中，它却是一个比较常用的字符串匹配算法。为什么这么说呢？原因有两点。

• 第一，实际的软件开发中，大部分情况下，模式串和主串的长度都不会太长。而且每次模式串与主串中的子串匹配的时候，当中途遇到不能匹配的字符的时候，就可以就停止了，不需要把 m 个字符都比对一下。所以，尽管理论上的最坏情况时间复杂度是 O(n*m)，但是，统计意义上，大部分情况下，算法执行效率接近于O(n+m )。
• 第二，暴力字符串匹配算法思想简单，代码实现也非常简单。简单意味着不容易出错，如果有 bug 也容易暴露和修复。在工程中，在满足性能要求的前提下，简单是首选。这也是我们常说的KISS（Keep it Simple and Stupid）设计原则。

3.2、KMP算法

KMP算法是由克努特（Knuth）、莫里斯（Morris）和普拉特（Pratt）共同设计实现的，因此简称为KMP算法。

3.2.1、核心思想

KMP算法的核心思想是：每当一趟匹配过程中出现字符比较不等时，不回溯主串指针，而是利用已经得到的“部分匹配”的结果将模式串向右“滑动”尽可能远的一段距离后，继续进行比较。

下面，我们先从具体的例子看起。

回顾BF算法中的匹配示例，在第三趟匹配中，当i=7、j=5字符比较不等时，又从i=4、j=1重新开始比较。

经仔细观察可发现，i=4和j=1，i=5和j=1，以及i=6和j=1这3次比较都是不必进行的。因为从第三趟的部分匹配结果就可得出，主串中第4个、第5个和第6个字符必然是“b”、“c”和“a”（即模式串中第2个、第3个和第4个字符）。而模式中的第一个字符是“a”，所以它无需再和这3个字符进行比较，仅需将模式向右滑动3个字符的位置继续进行i=7、j=2时的字符比较即可。

同理，在第一趟匹配中出现字符不等时，仅需将模式向右移动两个字符的位置继续进行i=3、j=1时的字符比较。由此，在整个匹配过程中，指针i没有回溯。整个匹配过程如下所示：

3.2.2、基本原理

现在讨论一般情况。假设主串为"$s_1$$s_2$…$s_n$ "，模式串为"$t_1$$t_2$…$t_n$ "，从上面的分析可知，为了实现改进算法，需要解决一个问题：当匹配过程中产生“失配”（即$s_i$不等于$t_i$ ）时，模式串可“向右滑动”的距离有多远。换句话说，当主串中第i个字符与模式串中第j个字符“失配”（即比较不等）时，主串中第i个字符应与模式串中的哪个字符再比较？

假设此时应与模式串中第k（k<j ）个字符继续比较，则模式串中前k - 1个字符子串必须满足下列关系式，且不可能存在k’ >k 满足下列关系式：

$$“s_{i-k+1}s_{i-k+2}...s_{i-1}”=“t_{1}t_{2}...t_{k-1}”$$

而已经得到的“部分匹配”的结果是

$$“s_{i-k+1}s_{i-k+2}...s_{i-1}”=“t_{j-k+1}t_{j-k+2}...t_{j-1}”$$

由以上两式可推得下列等式

$$“t_{1}t_{2}...t_{k-1}”=“t_{j-k+1}t_{j-k+2}...t_{j-1}”$$

这也就是说，若模式串中存在两个子串满足该关系式，则当匹配过程中，主串中第i个字符与模式串中第j个字符比较不等时，仅需将模式串向右滑动至模式串中第k个字符和主串中第i个字符对齐，此时，模式串中前k −1个字符的子串"$t_1$$t_2$…$t_{k-1}$ "必定与主串中第i个字符之前长度为k −1的子串“$t_{i-k+1}$$t_{i-k+2}$…$t_{i-1}$”相等，由此，匹配仅需从模式串中第k个字符与主串中第i个字符开始，依次向后进行比较。

若令next[j]=k，则next[j]表明当模式串中第j个字符与主串中相应字符“失配”时，在模式串中需重新和主串中该字符进行比较的字符的位置。由此，可引出模式串的next函数的定义：

$$next[j] = \begin{cases} 0\quad(“部分匹配”结果为空，即t_1与s_i不等，下一步进行t_1与s_{i+1}的比较) \\ 1\quad(“部分匹配”结果中，不存在相同的子串，下一步进行t_1和s_i的比较) \\ Max\{k|1<k<j\}\quad(“部分匹配”结果中，存在相同的子串，且k满足“t_{1}t_{2}...t_{k-1}”=“t_{j-k+1}t_{j-k+2}...t_{j-1}”，下一步进行t_k与S_i的比较） \end{cases}$$

由此定义可推出模式串的next函数值，如下示例：

说明：

• 当j=1时，“部分匹配”结果为空，因此下一步进行$t_1$与$s_{i+1}$的比较；
• 当j=2时，“部分匹配”结果中不存在相同的子串，因此下一步进行$t_1$和$s_i$的比较；
• 当j=3时，“部分匹配”结果中不存在相同的子串，因此下一步进行$t_1$和$s_i$的比较；
• 当j=4时，“部分匹配”结果中存在一个最长前缀子串”a“和一个最长后缀子串"a"相等，因此下一步进行$t_2$和$s_i$的比较；
• 当j=5时，“部分匹配”结果中存在一个最长前缀子串”a“和一个最长后缀子串"a"相等，因此下一步进行$t_2$和$s_i$的比较；
• 当j=6时，“部分匹配”结果中存在一个最长前缀子串”ab“和一个最长后缀子串"ab"相等，因此下一步进行$t_3$和$s_i$的比较；
• 当j=7时，“部分匹配”结果中不存在相同的子串，因此下一步进行$t_1$和$s_i$的比较；
• 当j=8时，“部分匹配”结果中存在一个最长前缀子串”a“和一个最长后缀子串"a"相等，因此下一步进行$t_2$和$s_i$的比较；

3.2.3、算法描述

有了模式串的next函数之后，匹配过程可按如下步骤进行：

• 以指针i和j分别指示主串和模式串中正待比较的字符，令i的初值为pos，j 的初值为1；
• 如果两个串均未比较到串尾，即i和j均分别小于等于主串和模式串的长度时，则循环执行以下操作：
  • 若$s_i$=$t_j$，则i和j分别增1，
  • 否则，i不变，而j退到next[j]的位置再比较；再比较时若相等，则指针各自增1，否则j再退到下一个next值的位置；依次类推，直至下列两种情况：
    • j 退到某个next值时字符比较相等，则指针各自增1，继续进行匹配
    • j 退到值为零（即模式串的第一个字符“失配”），则此时需将模式串继续向右滑动一个位置，即从主串的下一个字符$s_{i +1}$ 起和模式串$t_1$重新开始匹配。

相应的算法描述为：

// 利用模式串T的next函数求T在主串S中第pos个字符之后的位置
// 其中，T非空，1<=pos<=S.length
int Index_KMP(SString S, SString T, int pos) {
    i=pos; j=1;
    
    while(i<=S.length && j<=S.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;
}

KMP算法在形式上和BF算法极为相似。不同之处仅在于：当匹配过程中产生“失配”时，指针i不变，指针j退回到next[j]所指示的位置上重新进行比较，并且当指针j退至零时，指针i和指针j需同时增1，即若主串的第i个字符和模式的第1个字符不等，应从主串的第i+1个字符起重新进行匹配。KMP算法的匹配过程如下所示：

说明：

• 在第1趟匹配中，从i=1，j=1开始进行匹配，当i=2，j=2时出现不匹配，因此，进行第2趟匹配；
• 第2趟匹配，从i=2（指针i不变），j=1(next[2]=1)开始匹配，当i=2，j=1时出现不匹配，因此，进行第3趟匹配；
• 因为在第2趟匹配中，j=1时出现不匹配，所以第3趟匹配从i=3（指针i不变），j=1开始，直到i=8，j=6时出现不匹配，因此，进行第4趟匹配；
• 第4趟匹配，从i=8（指针i不变），j=3(next[6]=1)开始匹配，一直比较到了模式串的末尾，匹配成功，返回。

3.2.4、next函数

KMP算法是在已知模式串的next函数值的基础上执行的，那么，该如何求得模式串的next函数值呢？

从上述讨论可知，next函数值仅取决于模式串本身，和相匹配的主串无关。因此，可从分析next函数的定义出发，用递推的方法求得next函数值。

由定义可知：

$$next[1]=0 \tag{等式1}$$

设next[j]=k，这表明在模式串中存在下列关系：

$$“t_{1}t_{2}...t_{k-1}”=“t_{j-k+1}t_{j-k+2}...t_{j-1}”$$

其中k 为1<k <j 的某个值，并且不可能存在k '>k 满足该等式。此时next[j+1]的值可能有以下两种情况。

（1）若 $t_k$=$t_j$ ，则表明在模式串中

$$“t_{1}t_{2}...t_k”=“t_{j-k+1}t_{j-k+2}...t_j”$$

并且不可能存在k '>k 满足该等式，这就是说next[j+1]=k+1，即

$$next[j+1]=next[j]+1 \tag{等式2}$$

（2）若 $t_k$ ≠$t_j$ ，则表明在模式串中

$$“t_{1}t_{2}...t_k”≠“t_{j-k+1}t_{j-k+2}...t_j”$$

此时可把求next函数值的问题看成是一个模式匹配的问题，整个模式串既是主串又是模式串，而在当前的匹配过程中，已有"$t_{j-k+1}$$t_{j-k+2}$…$t_{j-1}$ "="$t_1$$t_2$…$t_{k-1}$ "，则当$t_j$ ≠$t_k$时应将模式串向右滑动至以模式串中的第next[k]个字符和主串中的第j个字符相比较。

若next[k]=k’ ，且$t_j$ =$t_{k'}$ ，则说明在主串中第j+1个字符之前存在一个长度为k’ （即next[k]）的最长子串，和模式串中从首字符起长度为k '的子串相等，即

$$“t_{1}t_{2}...t_{k'}”=“t_{j-k'+1}t_{j-k'+2}...t_j”\quad(1<k'<k<j) \tag{等式3}$$

这也就是说next[j +1]=k’ +1，即

$$next[j+1] = next[k]+1 \tag{等式4}$$

同理，若$t_j$≠$t_{k'}$ ，则将模式串继续向右滑动直至模式串中第next[k’]个字符和$t_j$对齐，…，依次类推，直至$t_j$和模式串中某个字符匹配成功或者不存在任何k’ (1<k’ <j ) 满足等式3，则

$$next[j+1]=1 \tag{等式5}$$

如下所示的模式串，已求得前6个字符的next函数值，现求next[7]，因为next[6]=3，又因$t_6$≠$t_3$ ，则需比较$t_6$和$t_1$（因为next[3]=1），这相当于将子串模式向右滑动。由于$t_6$≠$t_1$，且next[1]=0，所以next[7]=1，而因为$t_7$=$t_1$，则next[8]=2。

根据上述分析所得结果(即等式1、等式2、等式4和等式5)，仿照KMP算法，可得到求next函数值的算法：

// 求模式串T的next函数值，并将其存入数组next
void get_next(SString T, int next[]) {
    i=1; next[1]=0; j=0;
    
    whlie(i<T.length) {
        if(j==0 || T.ch[i]==T.ch[j]) {++i;++j;next[i]=j;}
        else j=next[j];
    }
}

该算法的时间复杂度为O(m)。通常，模式串的长度m比主串的长度n要小得多，因此，对整个匹配算法来说，增加的这点时间是值得的。

这里我们要注意的是，上述next函数在某些情况下存在效率问题。例如模式串“aaaab”在和主串“aaabaaaab”匹配时，当i=4、j=4时s.ch[4]≠t.ch[4]，根据next[j]的值还需进行i=4和j=3、i=4和j=2、i=4和j=1这3次比较。但实际上，因为在模式串中第1～3个字符和第4个字符都相等，因此模式串中第1～3个字符不需要再和主串中第4个字符相比较，而可以将模式串连续向右滑动4个字符的位置直接进行i=5、j=1时的字符比较。

这就是说，若按上述定义得到next[j]=k ，而模式中$t_j$=$t_k$ ，则当主串中字符$t_i$和$t_j$比较不等时，不需要再和$t_k$进行比较，而直接和$t_{next[k]}$进行比较，换句话说，此时的next[j]应和next[k]相同。由此可得计算next函数修正值的算法：

// 求模式串T的next函数修正值，并将之存入数组nextval
void get_nextval(SString T, int nextval[]) {
    i=1; nextval[1]=0; j=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[i];
    }
}

如下示例，是next函数修正值的计算结果：

3.2.5、复杂度分析

KMP 算法只需要一个额外的 next 数组，数组的大小跟模式串相同。所以空间复杂度是 O(m)，m 表示模式串的长度。

KMP 算法包含两部分，第一部分是构建 next 数组，第二部分才是借助 next 数组匹配。所以，关于时间复杂度，我们要分别从这两部分来分析。

• 计算next数组的代码的时间复杂度和模式串的长度（假设为m）有关，其时间复杂度是 O(m)。
• 借助next数组匹配的时间复杂度和主串的长度（假设为n）有关，其时间复杂度是 O(n)。

所以，综合两部分的时间复杂度，KMP算法的时间复杂度就是O(m+n)。

3.2.6、小结

KMP算法仅当模式与主串之间存在许多“部分匹配”的情况下，才显得比BF算法快得多。KMP算法的最大特点是指示主串的指针不需回溯，整个匹配过程中，对主串仅需从头至尾扫描一遍，这对处理从外设输入的庞大文件很有效，可以边读入边匹配，而无需回头重读。

四、总结

串是一种特殊的线性表，其特殊性体现在数据元素是一个字符，也就是说，串是一种内容受限的线性表，它限定了表中的元素为字符。串有两种基本存储结构：顺序存储和链式存储，但多采用顺序存储结构。串的常用算法是模式匹配算法，主要有BF算法和KMP算法。BF算法实现简单，但存在回溯，效率低，时间复杂度为O(m*n)。KMP算法对BF算法进行改进，消除回溯，提高了效率，时间复杂度为O(m+n)。

五、参考

《数据结构（C语言版 第2版）》

《数据结构与算法之美》