第六章：串——字符串的底层逻辑与匹配艺术

串，说白了就是字符串。在C语言里，我们天天跟它打交道——从命令行参数到文本解析，从协议处理到日志输出，串无处不在。但很多人写了好几年代码，对串的理解还停留在「char数组」这个层面。今天我们就把它彻底讲透。

核心要点：串是一种特殊的线性表，它的数据元素只能是字符。别小看这个限制，正是这个特性让串有了自己独特的存储结构和算法体系。

6.1 串的定义与基本概念

串（String）是由零个或多个字符组成的有限序列。记作：S = "a1 a2 ... an"，其中S是串名，引号内的字符序列是串值。

几个关键术语你得记住：

  • 空串：长度为0的串，写作""。注意和空格串" "区分，空格串长度不为0。
  • 子串：串中任意连续字符组成的子序列。比如"ello"是"Hello"的子串。
  • 主串：包含子串的串。
  • 位置：字符在串中的序号，通常从1开始计数（C语言习惯从0开始，但教材里常从1开始，注意区分）。

我个人习惯在嵌入式项目里用从0开始的位置，因为和数组下标一致，不容易出错。但如果你在写算法题，建议按教材来，免得扣分。

6.2 串的存储结构

串的存储结构有两种主流方式：顺序存储和链式存储。嗯，这里要注意，选择哪种取决于你的应用场景。

6.2.1 顺序存储

用一组连续的存储单元存放串的字符序列。C语言里最典型的就是char数组。

#define MAXLEN 255
typedef struct {
    char ch[MAXLEN];  // 存储串的数组
    int length;       // 串的实际长度
} SString;

这种方式的优点是随机存取快，缺点是长度固定。我在做串口协议解析时遇到过一个问题：协议帧长度不确定，用固定数组要么浪费空间，要么溢出。后来我改用动态分配的方式：

typedef struct {
    char *ch;    // 动态分配
    int length;
} HString;

我的建议：如果串的最大长度能确定，用SString；如果长度变化大，用HString。别为了省事一律用动态分配，嵌入式环境里malloc/free是有代价的。

6.2.2 链式存储

用链表存储串，每个节点存放若干字符。这种结构在插入删除时方便，但存储密度低。

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

typedef struct {
    Chunk *head, *tail;
    int length;
} LString;

说实话，链式串在实际项目中用得不多。我曾经在一个文本编辑器项目里试过，结果发现频繁的指针操作让代码变得很脆弱，最后还是换回了顺序存储。

6.3 串的模式匹配算法

模式匹配，说白了就是「找子串」。给定主串S和模式串T，判断T是否是S的子串，并返回位置。这是串操作里最核心的问题。

为什么重要？文本搜索、关键词匹配、DNA序列分析、网络入侵检测……几乎所有涉及字符串处理的场景都离不开模式匹配。

6.3.1 BF算法（暴力匹配）

BF算法，全称Brute-Force，也叫朴素匹配。思路很简单：从主串的第一个字符开始，逐个和模式串比较，如果匹配失败，主串回溯到下一个位置，模式串回到开头，重新比较。

int BF(char S[], char T[]) {
    int i = 0, j = 0;
    while (S[i] != '\0' && T[j] != '\0') {
        if (S[i] == T[j]) {
            i++; j++;
        } else {
            i = i - j + 1;  // 主串回溯
            j = 0;          // 模式串重置
        }
    }
    if (T[j] == '\0')
        return i - j;
    else
        return -1;
}

BF算法的时间复杂度是O(n*m)，n是主串长度，m是模式串长度。最坏情况下，比如主串是"AAAAAAAAAB"，模式串是"AAAB"，每次匹配到最后一个字符才失败，然后回溯，效率极低。

我曾经踩过的坑：在一个日志分析工具里用了BF算法，日志文件有几百MB，模式串是"ERROR"。结果程序跑了十几分钟还没出结果。后来一分析，日志里大量"ERR"开头的单词，导致频繁回溯。换KMP后，几秒就搞定了。

6.3.2 KMP算法

KMP算法由Knuth、Morris和Pratt三位大神提出，核心思想是：利用已经匹配过的信息，不让主串回溯。

为什么会这样？你想想看，BF算法的问题在于，每次匹配失败后，主串的i要回退，模式串的j要归零。但很多时候，我们已经知道前面哪些字符是匹配的，这些信息完全可以利用起来。

KMP的关键是next数组，它记录了模式串中每个位置之前的子串的最长相等前后缀长度。

举个例子，模式串"ABABAA"的next数组：

位置j 123456
模式串 ABABAA
next[j] 011234

next数组的计算方法：

void getNext(char T[], int next[]) {
    int i = 1, j = 0;
    next[1] = 0;
    while (i < T[0]) {  // T[0]存放模式串长度
        if (j == 0 || T[i] == T[j]) {
            i++; j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

有了next数组，KMP的匹配过程就简单了：

int KMP(char S[], char T[], int next[]) {
    int i = 1, j = 1;
    while (i <= S[0] && j <= T[0]) {
        if (j == 0 || S[i] == T[j]) {
            i++; j++;
        } else {
            j = next[j];  // 主串不回溯，只移动模式串
        }
    }
    if (j > T[0])
        return i - T[0];
    else
        return -1;
}

KMP的时间复杂度是O(n+m)，比BF的O(n*m)好太多了。而且主串指针i永不回溯，这在处理流式数据时特别有用——你不需要把数据存下来，边读边匹配就行。

我的经验：KMP的next数组计算容易出错，建议先手算几个例子验证。我一般会在纸上画一遍"ABABAA"的匹配过程，确保next数组正确后再写代码。另外，实际工程中还有改进版的nextval数组，能进一步优化某些特殊情况。

6.4 知识体系总览

下面这张图把本章的核心内容串起来了，你可以对照着复习：

串的知识体系 串的定义 存储结构 顺序存储（SString） 链式存储（LString） 模式匹配算法 BF算法（暴力匹配） KMP算法（next数组） 核心：利用已匹配信息，避免主串回溯

这张图把串的知识分成了三个层次：定义→存储→算法。你从顶层往下看，每个层次都有对应的技术选型。我个人建议初学者先把BF算法写熟练，理解回溯的代价，然后再去啃KMP。直接上KMP容易懵。

总结一下：串不是简单的字符数组，它有自己的一套理论和算法。BF算法是基础，KMP算法是进阶。在实际项目中，如果模式串很短（比如长度小于10），BF完全够用；如果模式串长且匹配频繁，KMP是更好的选择。

好了，串的内容就讲到这里。记住，理解KMP的关键是next数组，而理解next数组的关键是「最长相等前后缀」。把这个概念吃透了，KMP就没什么神秘的了。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →