第1章 串：从定义到KMP，我踩过的那些坑

串，说白了就是字符串。在C语言里，我们天天跟它打交道。但你真的懂它吗？

我记得刚入行那会儿，总觉得字符串操作不就是strcpy、strcmp那点事吗？直到有一次，我在一个嵌入式项目里处理日志解析，因为模式匹配效率太低，整个系统响应延迟飙升。嗯，从那以后，我再也不敢小看串了。

1.1 串的定义与基本操作

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

几个关键概念：

• 空串：长度为0的串，写作 ""
• 空格串：只包含空格的串，长度不为0
• 子串：串中任意连续字符组成的子序列
• 主串：包含子串的串

基本操作其实不多，但每个都很实用：

操作	说明
StrAssign(&T, chars)	生成一个值等于chars的串T
StrCopy(&T, S)	串复制，把S复制给T
StrEmpty(S)	判断串是否为空
StrLength(S)	返回串的长度
Concat(&T, S1, S2)	连接S1和S2，结果存到T
SubString(&Sub, S, pos, len)	取子串，从pos位置取len个字符
Index(S, T, pos)	定位子串T在主串S中的位置

1.2 串的存储结构

串有两种存储方式：顺序存储和链式存储。我个人更常用顺序存储，原因很简单——内存连续，访问快。

顺序存储

#define MAXLEN 255
typedef struct {
    char ch[MAXLEN + 1];  // 多一个位置存'\0'
    int length;           // 串的实际长度
} SString;

这种结构下，ch[0]到ch[length-1]存字符，ch[length]放'\0'。你想想看，这样既兼容了C语言的字符串习惯，又能快速获取长度。

链式存储

typedef struct StringNode {
    char ch[4];           // 每个结点存4个字符
    struct StringNode *next;
} StringNode, *LinkString;

链式存储的好处是插入删除方便，但缺点也很明显——存储密度低。每个结点都带一个指针，如果每个结点只存1个字符，那存储密度只有1/5。所以我一般建议每个结点存4~8个字符，平衡一下空间和时间。

1.3 朴素模式匹配算法

朴素匹配，也叫暴力匹配。思路很简单：从主串的每个位置开始，依次比较子串的每个字符。

int Index_BF(SString S, SString T, int pos) {
    int 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;
}

这个算法的时间复杂度是O(n*m)。最坏情况是什么？比如主串是"AAAAAAAAAB"，子串是"AAAB"，每次匹配到最后一个字符才发现不对，然后回溯。效率确实低。

但说实话，在大多数实际场景下，朴素匹配并不慢。我做过测试，对于随机文本，平均比较次数远小于最坏情况。所以别一上来就否定它。

1.4 KMP算法详解

KMP算法的核心思想就一句话：主串指针不回溯。

你想想看，朴素匹配为什么慢？因为每次匹配失败，主串指针都要往回跳。KMP利用已经匹配过的信息，让子串自己滑动到合适的位置。

next数组

next[j]表示：当子串第j个字符匹配失败时，子串应该从哪个位置继续匹配。

void get_next(SString T, int next[]) {
    int i = 1, j = 0;
    next[1] = 0;
    while (i < T.length) {
        if (j == 0 || T.ch[i] == T.ch[j]) {
            i++; j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

这里有个细节：next[1] = 0，表示第一个字符就不匹配，主串指针要前进一位。next[2] = 1，因为第二个字符不匹配时，只能从第一个字符重新开始。

nextval数组

nextval是对next的优化。举个例子：子串是"aaaab"，next数组是[0,1,2,3,4]。当第4个'a'匹配失败时，next[4]=3，但第3个也是'a'，肯定也匹配失败。这就多了一次无意义的比较。

void get_nextval(SString T, int nextval[]) {
    int i = 1, j = 0;
    nextval[1] = 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[j];
        }
    }
}

说白了，nextval就是在next的基础上，加了一步"如果回退后的字符和当前字符相同，就继续回退"。这样能避免重复比较。

KMP匹配过程

int Index_KMP(SString S, SString T, int pos) {
    int i = pos, j = 1;
    int next[MAXLEN];
    get_next(T, next);
    while (i <= S.length && j <= T.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;
}

你看，主循环里主串指针i只增不减，这就是KMP高效的原因。时间复杂度O(n+m)，比朴素匹配好太多了。

1.5 知识体系总览

下面这张图是我梳理的串相关知识点结构，方便你整体把握：

从这张图能看出来，串的核心就两块：怎么存、怎么匹配。存储结构决定了操作效率，匹配算法决定了查找速度。我个人建议你先把顺序存储和朴素匹配吃透，再啃KMP。别一口吃个胖子。

好了，串的基础知识就聊到这儿。记住，理解串的关键在于理解它的操作特性和匹配思想。KMP虽然看起来复杂，但核心就是"主串不回溯"这五个字。你品，你细品。

---

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