Sherfiter's wiki for fun

第 4 章 · 串与数组

这一章的两位主角看起来平淡,却各藏一个「降维打击」级别的算法。串(字符串)的问题是搜索:编辑器里 Ctrl+F 每天在用,KMP 把朴素匹配的 O(n·m) 压到 O(n+m),靠的是「失败时别浪费已匹配的信息」这个观察。数组的问题是存储:对称矩阵、稀疏矩阵存满整个 n² 是浪费,压缩存储用下标映射把空间砍掉大半。两个主题一个省时间一个省空间,恰好构成数据结构课的另一半世界观(前面几章基本在谈怎么组织,这章谈怎么利用数据的规律)。

4.1 朴素匹配:先跑一遍坏例子

C 里的串是 '\0' 结尾的 char 数组(C 指针课第 6 章讲过它的所有坑),匹配问题:主串 t(长 n)中找模式 p(长 m)首次出现的位置。朴素做法:主串每个起点,逐字符比对,失配就从头再来:

int naive(const char *t, const char *p) {
    int n = strlen(t), m = strlen(p);
    for (int i = 0; i + m <= n; i++) {       // 每个可能的起点
        int j = 0;
        while (j < m && t[i + j] == p[j]) j++;
        if (j == m) return i;
    }
    return -1;
}

一般文本它挺好(平均比对次数远小于 n·m),但构造 t = "aaaaaab"、p = "aaab":每个起点都要比对到最后一个字符才失败,主串指针 i 还得回退,最坏 O(n·m)。朴素版的「罪」在浪费:失配前已经比对了那么多字符,它们明明证明了「主串接下来的一段长什么样」,却全被扔掉了。

4.2 KMP:失败信息别丢,主串指针永不回退

KMP 的核心观察用例子讲。模式 p = "ababc",在主串某处比对了前 4 个字符 abab 后失配(主串下一个是 a,模式的第 5 个是 c):

主串:  ... a b a b a ...
模式:      a b a b c
                    ↑ 失配在这
已匹配的 "abab" 有一个性质:它的最长相等前后缀是 "ab"(前 2 位 = 后 2 位)
→ 主串中刚比对过的后两位 "ab" 可以直接当作新一轮已匹配的前缀!

也就是说:失配后,主串指针原地不动,模式指针跳到「已匹配部分的最长相等前后缀」长度处接着比。这个「跳到哪」的信息与主串无关,只看模式自己,可以预处理成 next 数组:

void get_next(const char *p, int *next, int m) {
    next[0] = -1;                       // next[j]: p[0..j-1] 的最长相等前后缀长度
    int i = 0, j = -1;
    while (i < m - 1) {
        if (j == -1 || p[i] == p[j]) next[++i] = ++j;
        else j = next[j];               // 自己找自己的最长相等前后缀,递归跳
    }
}

int kmp(const char *t, const char *p) {
    int n = strlen(t), m = strlen(p);
    int next[m]; get_next(p, next, m);
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (j == -1 || t[i] == p[j]) { i++; j++; }   // 配上或模式从头,双指针前进
        else j = next[j];                            // 失配:模式指针跳,i 不动
    }
    return j == m ? i - m : -1;
}

主串指针 i 从头到尾只增不减,所以主串侧 O(n);next 的构造(模式自己跟自己跑 KMP)O(m),合计 O(n+m)。构造 next 时「j = next[j]」这行初次看很玄:求「p[0..i] 的最长相等前后缀」,等价于「在 p 自己身上跑一遍匹配」,想通这一层,整个算法就通了。工程备注:实战的字符串搜索多 Boyer-Moore、Sunday 这类(坏字符启发,平均更快),KMP 的价值在于它是最优雅的「不回退」思想,而且 next 数组还衍生出「最短循环节」「字符串周期」这些分析工具。

4.3 数组压缩:有规律就不存重复

矩阵存储的浪费分两类,各有压缩术。

有规律的方阵(对称、三角):下三角存进一维数组,靠下标映射还原。对称矩阵 A‘ij‘=A‘ji‘A_`{ij}` = A_`{ji}`,只存下三角 n(n+1)/2n(n+1)/2 个元素(近省一半),读上半时翻一下:

// 下三角按行优先存入一维数组 b
int sym_get(const int *b, int i, int j, int n) {
    if (i < j) { int t = i; i = j; j = t; }   // 用对称性换到下三角
    return b[i * (i + 1) / 2 + j];            // 前 i 行共 i(i+1)/2 个,行内第 j 个
}

映射公式 i(i+1)/2 + j 值得亲手推一遍(数一数第 i 行之前攒了多少个),考试爱考,推导本身就是「二维到一维」坐标变换的练习。

稀疏矩阵:非零元素占比极低(如图结构、有限元的刚度矩阵),n² 存满九成是零。解法只存非零三元组 (行, 列, 值),顺带牺牲 O(1) 随机访问(找某个元素要扫表或建索引),换来存储从 O(n²) 掉到 O(t)(t 为非零元数)。现代稀疏格式(CSR:按行压缩的三元组)是所有图计算、机器学习稀疏运算的地基,PyTorch 的 sparse tensor、图数据库的邻接结构,思想上全是这章的三元组。

常见错误

  • next 数组的语义记混。next[j] 是「p[0..j-1]」的最长相等前后缀(不含 p[j] 自己),有的教材版本又整体偏移一位。背结论不如现场推小例子(p = "abab" 手算一遍)。
  • strlen 放进循环条件。for (i = 0; i < strlen(t); i++) 每轮重新数一遍串长,把 O(n) 的循环写成 O(n²);先存下 n。
  • 压缩矩阵忘了映射的对称分支。sym_get 不处理 i 小于 j 的情况直接返回,读到的是错位数据,还往往不报错,bug 极难定位。

练习

  1. 手算:模式 "aabaab" 的 next 数组(写出每一步的最长相等前后缀),再用它匹配主串 "aabaabaabaab"。
  2. 手算:n = 5 的对称矩阵,写出下三角元素存入一维数组后的位置表,验证 A[2][4] 和 A[4][2] 都映射到同一个下标。
  3. 动手:对比朴素与 KMP:主串 "a"*50000 + "b",模式 "a"*50 + "b",各计时,量一量差距。
  4. 思考:编辑器搜索(如 ripgrep)为什么不追求 O(n+m) 的 KMP,反而用 SIMD 并行比对的朴素法?提示:常数、内存带宽、以及「实际文本失配很快」三个角度。
豫ICP备2026027944号