11. 串：从定义到KMP，一场关于字符串的深度对话

大家好，我是你们的老朋友。今天我们来聊聊串——也就是字符串。说实话，串这个东西，在C语言里是个让人又爱又恨的存在。爱它是因为几乎所有实用程序都离不开它，恨它是因为……嗯，你想想看，一个字符数组就能搞定的东西，为什么我们要专门开一章来讲？

别急，等你看完KMP算法的精妙之处，就会明白我的意思了。

11.1 串的定义：不只是字符数组

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

这里有几个关键概念，我建议你记牢：

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

11.2 串的存储结构：两种流派

串的存储，说白了就两种方式。我个人更偏爱第二种，但第一种在某些场景下也有它的优势。

11.2.1 定长顺序存储

用固定长度的字符数组来存储串。比如：

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

这种方式的优点是简单、访问快。但缺点也很明显——长度固定，容易溢出。我在早期做嵌入式开发时，就吃过这个亏。当时解析一个GPS数据帧，没注意长度检查，结果缓冲区溢出，整个系统直接挂了……嗯，从那以后我再也不敢轻视边界检查了。

11.2.2 堆分配存储

用动态内存分配来存储串，长度可以动态变化：

typedef struct {
    char *ch;
    int length;
} HString;

使用时需要手动管理内存：

void InitString(HString *S) {
    S->ch = NULL;
    S->length = 0;
}

void StrAssign(HString *S, const char *chars) {
    if (S->ch) free(S->ch);
    int len = strlen(chars);
    S->ch = (char *)malloc((len + 1) * sizeof(char));
    strcpy(S->ch, chars);
    S->length = len;
}

这种方式的灵活性更高，但你要小心内存泄漏。我建议你养成一个习惯：谁分配，谁释放。

11.3 朴素的模式匹配算法

模式匹配，就是在一个主串中查找一个子串（模式串）的位置。最直接的方法，就是暴力匹配。

算法思路很简单：从主串的第一个字符开始，与模式串的第一个字符比较。如果相等，继续比较下一个；如果不相等，主串回溯到第二个字符，模式串回到开头，重新开始。

int Index_BF(const char *S, const char *T) {
    int i = 0, j = 0;
    int lenS = strlen(S);
    int lenT = strlen(T);
    
    while (i < lenS && j < lenT) {
        if (S[i] == T[j]) {
            i++; j++;
        } else {
            i = i - j + 1;  // 主串回溯
            j = 0;          // 模式串回到开头
        }
    }
    if (j == lenT) return i - j;  // 匹配成功
    else return -1;               // 匹配失败
}

这个算法的时间复杂度是O(n*m)，n为主串长度，m为模式串长度。最坏情况下，比如主串是 "AAAAAAAAAAAAAAB"，模式串是 "AAAB"，每次都要比较到最后一个字符才发现不匹配，然后回溯……效率极低。

11.4 KMP模式匹配算法

KMP算法由Knuth、Morris和Pratt三位大神提出。它的核心思想是：主串不回溯，模式串尽量少回溯。

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

11.4.1 next数组：KMP的灵魂

KMP的关键在于一个next数组。next[j]表示：当模式串中第j个字符匹配失败时，模式串应该跳到哪个位置继续匹配。

next数组的计算规则：

• next[0] = -1（C语言中，下标从0开始）
• next[1] = 0
• 对于j > 1，next[j] = 模式串前j-1个字符中，最长相等前后缀的长度

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

j	0	1	2	3	4	5
模式串	A	B	A	B	A	C
next[j]	-1	0	0	1	2	3

怎么算的？以j=4为例，前3个字符是 "ABA"，最长相等前后缀是 "A"，长度为1，所以next[4]=1。

11.4.2 计算next数组的代码

void GetNext(const char *T, int *next) {
    int len = strlen(T);
    next[0] = -1;
    int i = 0, j = -1;
    
    while (i < len - 1) {
        if (j == -1 || T[i] == T[j]) {
            i++; j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

这段代码看起来有点绕，但核心逻辑就是：用两个指针i和j，i往前走，j回溯。如果T[i]==T[j]，说明找到了一个更长的前后缀；否则j回退到next[j]的位置继续尝试。

11.4.3 KMP匹配过程

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

int Index_KMP(const char *S, const char *T) {
    int i = 0, j = 0;
    int lenS = strlen(S);
    int lenT = strlen(T);
    int *next = (int *)malloc(lenT * sizeof(int));
    GetNext(T, next);
    
    while (i < lenS && j < lenT) {
        if (j == -1 || S[i] == T[j]) {
            i++; j++;
        } else {
            j = next[j];  // 主串i不动，模式串j跳转
        }
    }
    free(next);
    if (j == lenT) return i - j;
    else return -1;
}

和朴素算法对比一下，区别就在else分支：朴素算法是 i = i - j + 1; j = 0;，而KMP是 j = next[j];。i没有回溯，j也没有归零，而是跳到了一个合理的位置。

11.4.4 时间复杂度分析

KMP的时间复杂度是O(n+m)。为什么？因为在整个匹配过程中，i只增不减，最多移动n次；j虽然会回溯，但每次回溯都会让j变小，而j总共增加的次数不超过n，所以回溯的总次数也不超过n。加上计算next数组的O(m)，总复杂度就是O(n+m)。

知识体系总览

下面这张图，是我为你梳理的本章知识结构：

好了，关于串的内容就讲到这里。从定义到存储，从朴素匹配到KMP，每一步都有它存在的道理。KMP的next数组确实需要花点时间消化，但一旦理解了它的「利用已匹配信息」这个核心思想，你会发现它其实很自然。

下次遇到字符串匹配的问题，你可以先问问自己：这个场景值得上KMP吗？如果值得，那就大胆用；如果不值得，朴素算法也挺好。毕竟，合适的才是最好的。

---

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