KMP算法及next推导

手法凯酱

1008人浏览 · 2025-12-28 16:10:47

手法凯酱 · 2025-12-28 16:10:47 发布

KMP 算法及 next 数组详细推导

KMP 算法基本思想

传统字符串匹配（朴素算法）时间复杂度:O(n×m)
KMP 算法时间复杂度:O(n+m)
核心思想：利用已匹配的信息，避免主串指针回溯

next 数组的严格定义

对于长度为 m 的模式串 P[1…m]：

在这里插入图片描述

通俗理解：
next[j] = 模式串前 j-1 个字符中，最长的相等前后缀的长度 + 1

手动计算 next 数组（以 “abaabcac” 为例）

模式串：a b a a b c a c

索引： 1 2 3 4 5 6 7 8

步骤 1：j = 1

P[1] = 'a'
规定：next[1] = 0
解释：第一个字符匹配失败时，主串指针右移

步骤 2：j = 2

前 1 个字符：'a'
前缀：无（不能是自身）
后缀：无
最长公共前后缀长度：0
next[2] = 0 + 1 = 1

步骤 3：j = 3

前 2 个字符：'a b'
前缀：'a'
后缀：'b'
最长公共前后缀：无（'a' ≠ 'b'）
长度：0
next[3] = 0 + 1 = 1

步骤 4：j = 4

前 3 个字符：'a b a'
前缀集合：'a', 'ab'
后缀集合：'ba', 'a'
相等的前后缀：'a' = 'a'
最长长度：1
next[4] = 1 + 1 = 2

步骤 5：j = 5

前 4 个字符：'a b a a'
前缀：'a', 'ab', 'aba'
后缀：'baa', 'aa', 'a'
相等的前后缀：'a' = 'a'
最长长度：1
next[5] = 1 + 1 = 2

步骤 6：j = 6

前 5 个字符：'a b a a b'
前缀：'a', 'ab', 'aba', 'abaa'
后缀：'baab', 'aab', 'ab', 'b'
相等的前后缀：'ab' = 'ab'（长度 2）
最长长度：2
next[6] = 2 + 1 = 3

步骤 7：j = 7

前 6 个字符：'a b a a b c'
前缀：'a', 'ab', 'aba', 'abaa', 'abaab'
后缀：'baabc', 'aabc', 'abc', 'bc', 'c'
相等的前后缀：无（注意：'a' ≠ 'c', 'ab' ≠ 'bc'...）
最长长度：0
next[7] = 0 + 1 = 1

步骤 8：j = 8

前 7 个字符：'a b a a b c a'
前缀：'a', 'ab', 'aba', 'abaa', 'abaab', 'abaabc'
后缀：'baabca', 'aabca', 'abca', 'bca', 'ca', 'a'
相等的前后缀：'a' = 'a'（长度 1）
最长长度：1
next[8] = 1 + 1 = 2

最终 next 数组：

j:       1 2 3 4 5 6 7 8
P[j]:    a b a a b c a c
next[j]: 0 1 1 2 2 3 1 2

KMP 匹配过程演示

主串 S = “acabaabaabcacaabc”

模式串 P = “abaabcac”

步骤主串 (i) 模式串 (j) 比较结果操作

S[1]=a P[1]=a a=a 匹配 i=2, j=2
S[2]=c P[2]=b c≠b 不匹配 j=next[2]=1
S[2]=c P[1]=a c≠a 不匹配 j=next[1]=0 → i=3, j=1
S[3]=a P[1]=a a=a 匹配 i=4, j=2
S[4]=b P[2]=b b=b 匹配 i=5, j=3
S[5]=a P[3]=a a=a 匹配 i=6, j=4
S[6]=a P[4]=a a=a 匹配 i=7, j=5
S[7]=b P[5]=b b=b 匹配 i=8, j=6
S[8]=a P[6]=c a≠c 不匹配 j=next[6]=3
S[8]=a P[3]=a a=a 匹配 i=9, j=4
S[9]=a P[4]=a a=a 匹配 i=10, j=5
S[10]=b P[5]=b b=b 匹配 i=11, j=6
S[11]=c P[6]=c c=c 匹配 i=12, j=7
S[12]=a P[7]=a a=a 匹配 i=13, j=8
S[13]=c P[8]=c c=c 匹配匹配成功！

匹配位置：13-8+1 = 6（从主串第6个字符开始匹配成功）

next 数组的优化（nextval 数组）

实际应用中常使用 nextval 数组进一步优化：

对于模式串 “abaabcac”：

j:       1 2 3 4 5 6 7 8
P[j]:    a b a a b c a c
next[j]: 0 1 1 2 2 3 1 2

nextval 计算规则：

nextval[1] = 0
对于 j>1：
· 如果 P[j] = P[next[j]]，则 nextval[j] = nextval[next[j]]
· 否则 nextval[j] = next[j]

计算过程：

· j=1: nextval[1]=0
· j=2: P[2]=b ≠ P[next[2]=1]=a → nextval[2]=next[2]=1
· j=3: P[3]=a = P[next[3]=1]=a → nextval[3]=nextval[next[3]=1]=0
· j=4: P[4]=a ≠ P[next[4]=2]=b → nextval[4]=next[4]=2
· j=5: P[5]=b ≠ P[next[5]=2]=b → 相等 → nextval[5]=nextval[2]=1
· j=6: P[6]=c ≠ P[next[6]=3]=a → nextval[6]=next[6]=3
· j=7: P[7]=a = P[next[7]=1]=a → nextval[7]=nextval[1]=0
· j=8: P[8]=c ≠ P[next[8]=2]=b → nextval[8]=next[8]=2

nextval: 0 1 0 2 1 3 0 2

代码实现

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// KMP 匹配算法
int kmp_search(const string& text, const string& pattern) {
    if (pattern.empty()) return 0;
    
    // 构建 nextval 数组
    int n = pattern.length();
    vector<int> next(n, 0);
    next[0] = -1;
    
    // 计算 next 数组
    int i = 0, j = -1;
    while (i < n - 1) {
        if (j == -1 || pattern[i] == pattern[j]) {
            i++; j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
    
    // 优化为 nextval
    for (int i = 1; i < n; i++) {
        if (pattern[i] == pattern[next[i]]) {
            next[i] = next[next[i]];
        }
    }
    
    // 开始匹配
    i = 0; j = 0;
    while (i < text.length() && j < n) {
        if (j == -1 || text[i] == pattern[j]) {
            i++; j++;
        } else {
            j = next[j];
        }
    }
    
    return j == n ? i - j + 1 : 0;
}

int main() {
    string text = "acabaabaabcacaabc";
    string pattern = "abaabcac";
    
    int pos = kmp_search(text, pattern);
    cout << "模式串: " << pattern << endl;
    cout << "主串: " << text << endl;
    cout << "匹配位置: " << pos << endl;
    
    return 0;
    }