《指针永不回首，直到与你相遇》 Verified

不知不觉，已经五月了。

这次的五一假期，我并没有安排任何远行。大部分时间还是待在学校图书馆。最近一直坐在靠窗那个固定的位置，下午阳光会斜着照进来，桌面很亮，坐久了甚至有点热。但是还好，图书馆 24 小时空调，而且成都的天气阴晴不定，虽说已经进入五月，逐渐有了一点热的意思，但是一天下来，出太阳的时间不是很长，大部分还是凉爽的阴天。

计组的一轮复习刚刚落下帷幕，便马不停蹄开始数据结构的复习，后续还有计网、计算机操作系统😫。前三章还算偏理论，线性表、栈、队列，更多是理解和记忆。但复习到第四章“串”的时候，终于开始真正接触到那些经典算法了。

最近也是刚刚学完第四章串的内容，便顺手写下这篇笔记（也发现好久没写了，上次的笔记已经是 2 月份得了），也算给这段备考生活留一点记录，毕竟算法这种东西，过两天不看可能又会变成“最熟悉的陌生人”。

在聊 KMP 之前，总得先想想最暴力、最直观的匹配逻辑是什么样的。比如我要在字符串 ABABCABAA 里找 ABAA，最简单的办法就是拿子串的第一位去对主串，对上了就看第二位，对不上就往后挪一个位置重新开始。这就是所谓的朴素模式匹配算法（也就是俗称的暴力破解）。

这种算法的代码写起来非常爽，逻辑简单暴力，不需要深度分析。但问题就在于，它太“笨”了。主串指针 $i$ 每次都要回溯，而子串指针 $j$ 也得从头开始。你想想，如果主串是 aaaaaaab，子串是 aaab，每次匹配到第四个字符发现不对，$i$ 指针又得退回到起始位置的下一位，这其中的 $O(n \times m)$ 的时间复杂度的重复劳动简直是计算机资源的极大浪费。

这就引入了今天的主角 ---- KMP Algorithm。其核心逻辑其实就一句话：主串指针 $i$ 永远不回溯，只移动子串指针 $j$。

它的发明者（Knuth, Morris, Pratt 三位大佬）发现，当我们匹配失败时，其实我们已经知道前面一部分字符是什么了。利用这个已知信息，我们可以直接把子串向后“滑”到一个合适的位置，而不是傻乎乎地退回原点。

这个“合适的位置”就是由 next 数组决定的。理解 next 数组的关键在于理解“最长相等前后缀”。看了两遍视频课，才终于听懂老师讲的“前缀”和“后缀”，其实就是找子串当前失败位置之前的那个部分里，开头和结尾长得一模一样的最长片段。

比如子串是 ABABC，如果在 C 这里匹配失败了，前面的部分是 ABAB。它的前缀有 $\{A, \ AB, \ ABA\}$，后缀有 $\{B, \ AB, \ BAB\}$。其中最长且相等的就是 AB，长度是 2。那么下一次匹配，我们就不必从子串的开头开始了，而是直接从第 3 个字符（索引为 2 的位置）开始，因为前面的 AB 已经默认对上了。这种利用已知信息的跳转，让时间复杂度直接降到了 $O(n + m)$，这种跳跃式的美感，确实是算法设计的魅力所在。

为了应对 408 考试那种对底层原理的严苛考察，用 C 语言手写一遍 KMP 是无可逃避的宿命。在 DEV-C++ 编辑器中，没有华丽的代码提示，一切逻辑都必须在脑海中异常清晰。最容易让人陷入自我怀疑的，往往是 get_next 函数中那个关于 $j = -1$ 的初始状态设定。

#include <stdio.h>
#include <string.h>

// 获取 next 数组
void get_next(char *p, int next[]) {
    int p_len = strlen(p);
    next[0] = -1; // 初始位设为 -1，方便统一逻辑
    int i = 0;    // 当前后缀末尾
    int j = -1;   // 前缀末尾（也代表最长相等前后缀的长度）

    while (i < p_len - 1) {
        if (j == -1 || p[i] == p[j]) {
            i++;
            j++;
            next[i] = j;
        } else {
            // 如果匹配失败，j 回退到上一个可能相等的前缀位置
            j = next[j];
        }
    }
}

// KMP 匹配过程
int KMP(char *s, char *p) {
    int i = 0; // 主串指针
    int j = 0; // 子串指针
    int s_len = strlen(s);
    int p_len = strlen(p);
    int next[p_len];
    
    get_next(p, next);

    while (i < s_len && j < p_len) {
        if (j == -1 || s[i] == p[j]) {
            i++;
            j++;
        } else {
            j = next[j]; // 关键：i 不动，j 回退
        }
    }

    if (j == p_len) {
        return i - j; // 匹配成功，返回起始下标
    }
    return -1;
}

写这段 C 代码时，我特别注意了数组下标。408 的教材里，有时候下标从 1 开始（$next[1] = 0$），有时候从 0 开始。在实际编程中，0 索引更符合我们的习惯，但考研做选择题时，一定得看清楚题目给的起始定义。这种细节如果丢分，那真是太冤了。

C 语言固然扎实，但如果用 C# 这种更为现代、语法更具表现力的语言来重构，也许更能贴合我日常开发的审美（毕竟我也是主攻 C# 的）。C# 剥离了那些繁琐的指针和内存管理负担，让我可以把全部的注意力倾注在算法逻辑本身。

using System;

public class KMPAlgorithm
{
    public static int[] GetNext(string pattern)
    {
        int[] next = new int[pattern.Length];
        next[0] = -1;
        int i = 0;
        int j = -1;

        while (i < pattern.Length - 1)
        {
            if (j == -1 || pattern[i] == pattern[j])
            {
                i++;
                j++;
                // 这里的逻辑和 C 语言一致，保持算法的纯粹性
                next[i] = j;
            }
            else
            {
                j = next[j];
            }
        }
        return next;
    }

    public static int Search(string text, string pattern)
    {
        if (string.IsNullOrEmpty(pattern)) return 0;
        
        int[] next = GetNext(pattern);
        int i = 0; // 主串索引
        int j = 0; // 模式串索引

        while (i < text.Length && j < pattern.Length)
        {
            if (j == -1 || text[i] == pattern[j])
            {
                i++;
                j++;
            }
            else
            {
                j = next[j];
            }
        }

        return j == pattern.Length ? i - j : -1;
    }
}

对比 C 语言和 C#，其实核心思想是一模一样的。但在 C# 里，我不用去担心内存越界或者手动管理 strlen 这种事情。写 C# 代码对我来说更像是一种“心理按摩”，能让我从繁杂的指针操作中暂时解脱出来，回归到算法本身的逻辑美感。

本以为理清了 next 数组就已经拿到了通往“串”世界的通行证，但当我翻到教材后面部分，看到那一个个连续重复的字符（比如模式串 aaaaab）时，才意识到原版 KMP 依然存在一点点冗余。

原版的 next 数组在遇到匹配失败时，会告诉指针 $j$ 跳回到前一个可能的位置。但如果回跳到的位置和当前字符一模一样呢？既然当前的 a 已经匹配失败了，跳到一个同样的 a 上去显然是徒劳的，指针还得接着跳。为了省去这多余的一步，$nextval$ 数组应运而生。

它像是一种“未雨绸缪”的优化：在构建 next 的过程中多看一眼。如果回跳后的字符与当前字符相同，那就干脆直接继承那个字符的跳跃路线。这种逻辑上的连环跨越，让算法从“知错能改”进化到了“不再重蹈覆辙”。

在 C 语言的底层实现中，这种逻辑的优化只在一念之间：

// 在 get_next 的基础上，进化为 get_nextval
void get_nextval(char *p, int nextval[]) {
    int p_len = strlen(p);
    nextval[0] = -1;
    int i = 0, j = -1;
    while (i < p_len - 1) {
        if (j == -1 || p[i] == p[j]) {
            i++; j++;
            // 核心优化：多看一眼
            if (p[i] != p[j]) {
                nextval[i] = j; // 字符不同，照常记录
            } else {
                // 字符相同，直接继承“前人的经验”，一跳到底
                nextval[i] = nextval[j];
            }
        } else {
            j = nextval[j];
        }
    }
}

复习到这一章，我深深感觉到 408 为什么被称为“计算机考研的天花板”。它不仅仅要求你背过这些公式，更要求你对每一个逻辑分支都有透彻的理解。比如 KMP 的 next 数组优化（即 $nextval$ 数组），当你发现

时，其实可以再往前跳一步。这种层层递进的优化，在复习时觉得头大，但在写代码时却觉得非常合理。

合上电脑，手腕发酸。

从2025年到2026年，这条路铺了这么久。上海交大还在对岸，专业课教材堆在桌角，脊背朝着我沉默地伫立。有时盯着那些书脊上的标题、看着屏幕上的日期，也会问自己：能坚持到底吗？

KMP 算法没有回答我。但它展示了一种活法：匹配失败是必然的，回退策略才是分水岭。只要掌握了正确的回退 —— 调整心态，重构节奏 —— 主串指针 $i$（那是时间，也是我本人）就永远不回头。

我打羽毛球。我练硬笔字。前者让焦虑挥发，后者让心沉下去。大汗淋漓与屏息凝神之间，是备考岁月里仅有的两片净土。

距离2026年12月，说远不远，说近不近。我能做的，就是像 KMP 里那个主串指针 $i$ 一样 —— 不为过去的失误回溯。提前构建好自己的 next 数组，做好总结和反思。哪怕至暗时刻，也能迅速找到下一个落脚点。

明天，把“串”收尾。然后去爬“树”。二叉树、红黑树、AVL——

指针永不回首。

直到与你相遇。

夜深了。继续往前走吧。

投喂·结缘

WeChat 长按或识别

Ali 长按或识别