信息学奥赛一本通1169：如何高效实现字符串匹配？

Question

在信息学奥赛一本通第1169题中，要求实现高效的字符串匹配。一个常见问题是：当使用朴素字符串匹配算法时，时间复杂度过高，在主串与模式串长度较大时容易超时。如何优化？能否结合KMP算法减少不必要的字符比较？关键在于理解next数组的构建原理：它记录模式串中每个位置前最长相等前后缀的长度，从而在失配时快速跳转，避免回溯主串指针。如何正确构造next数组并应用于匹配过程，是解决本题的核心难点。

Answer 1

1. 朴素字符串匹配的性能瓶颈分析

在信息学奥赛一本通第1169题中，常见的字符串匹配任务是判断模式串 P 是否在主串 S 中出现。若采用朴素（Brute Force）算法，其基本思想是从主串的每一个位置开始尝试与模式串逐字符比对。

该算法的时间复杂度为 O(n×m)，其中 n 是主串长度，m 是模式串长度。当两者均达到 1e5 级别时，最坏情况下的操作次数可达 1e10，明显超出时间限制。

例如，主串为 "aaaaab"，模式串为 "aaab"，每次匹配失败后主串指针需回退，导致大量重复比较。

2. KMP算法的核心思想与优势

KMP（Knuth-Morris-Pratt）算法通过预处理模式串构造 next 数组，实现主串指针不回溯，从而将时间复杂度优化至 O(n + m)。

其核心在于：当模式串在某位置失配时，利用已知的“最长相等前后缀”信息，跳过不可能成功的匹配位置。

例如，模式串 "ababa" 在第5位失配时，由于前缀 "aba" 与后缀 "aba" 相等，可直接将模式串右移两位继续匹配，避免从头开始。

3. next数组的定义与构建原理

next[i] 表示模式串前 i 个字符构成的子串中，最长相等真前后缀的长度。

构建过程使用双指针法：i 遍历模式串，j 记录当前最长前后缀长度。

i	模式串P[0:i]	最长相等前后缀	next[i]
0	a	-	0
1	ab	-	0
2	aba	a	1
3	abab	ab	2
4	ababa	aba	3
5	ababac	-	0

4. next数组的代码实现

void buildNext(const string& pattern, vector<int>& next) {
    int m = pattern.length();
    next[0] = 0;
    int j = 0;
    for (int i = 1; i < m; ++i) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = next[j - 1];
        }
        if (pattern[i] == pattern[j]) {
            j++;
        }
        next[i] = j;
    }
}

5. KMP匹配过程的流程图

graph TD A[开始匹配] --> B{S[i] == P[j]?} B -- 是 --> C[j++, i++] C --> D{j == m?} D -- 是 --> E[找到匹配位置 i-m] D -- 否 --> B B -- 否 --> F{j == 0?} F -- 是 --> G[i++] F -- 否 --> H[j = next[j-1]] H --> B G --> B

6. 完整KMP算法实现示例

• 输入：主串 S，模式串 P
• 输出：所有匹配起始位置
• 步骤：
• 1. 调用 buildNext 构建 next 数组
  2. 使用双指针遍历主串和模式串
  3. 失配时根据 next 数组调整 j
  4. 成功匹配时记录位置并继续

vector<int> kmpSearch(const string& text, const string& pattern) {
    vector<int> next(pattern.size());
    buildNext(pattern, next);
    
    vector<int> result;
    int n = text.length(), m = pattern.length();
    int i = 0, j = 0;
    
    while (i < n) {
        if (text[i] == pattern[j]) {
            i++; j++;
        }
        if (j == m) {
            result.push_back(i - j);
            j = next[j - 1];
        } else if (i < n && text[i] != pattern[j]) {
            if (j != 0) j = next[j - 1];
            else i++;
        }
    }
    return result;
}

7. 边界条件与常见陷阱

在实际编码中，以下几点容易出错：

• next[0] 必须初始化为 0
• while循环中 j > 0 的判断不可省略，否则数组越界
• 匹配成功后应使用 j = next[j-1] 继续查找所有匹配项
• 主串指针 i 仅在完全无法匹配且 j=0 时才自增

8. 性能对比与应用场景扩展

算法	时间复杂度	空间复杂度	适用场景
朴素匹配	O(n×m)	O(1)	小规模数据
KMP	O(n+m)	O(m)	大文本搜索
BM	平均O(n/m)	O(m)	编辑器查找
Rabin-Karp	O(n+m)	O(1)	多模式匹配

KMP特别适用于模式串固定、主串动态增长的场景，如DNA序列比对、日志关键词监控等。