字符串匹配KMP算法 | 程序员小乐

算法字符串 KMP

算法

发布日期: 2024-09-23

作者: 小乐

文章字数: 548

阅读时长: 2 分

阅读次数:

一、字符串匹配问题

1.1 问题定义

在文本串 text 中查找模式串 pattern 的出现位置。

1.2 暴力解法

public int bruteForce(String text, String pattern) {
    for (int i = 0; i <= text.length() - pattern.length(); i++) {
        int j = 0;
        while (j < pattern.length() && text.charAt(i + j) == pattern.charAt(j)) {
            j++;
        }
        if (j == pattern.length()) return i;
    }
    return -1;
}

时间复杂度：( O(mn) )

二、KMP核心思想

2.1 观察

当匹配失败时，模式串中已匹配的部分可能包含相同的前缀和后缀，可以直接利用这部分信息，避免文本串指针回溯。

2.2 示例

text:    a b a b a b c a
pattern: a b a b c
              ↑
            失配于第5位

已匹配: a b a b
最长相同前缀后缀: a b
可以直接将pattern移动到：
text:    a b a b a b c a
pattern:     a b a b c

三、next数组（前缀函数）

3.1 定义

next[i] 表示 pattern[0..i] 中最长的相等前缀后缀的长度。

3.2 构建

public int[] buildNext(String pattern) {
    int n = pattern.length();
    int[] next = new int[n];
    int j = 0;  // 前缀末尾
    
    for (int i = 1; i < n; i++) {
        while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
            j = next[j - 1];  // 回退
        }
        if (pattern.charAt(i) == pattern.charAt(j)) {
            j++;
        }
        next[i] = j;
    }
    return next;
}

3.3 示例

pattern: a b a b c a
next:    0 0 1 2 0 1

解释:
"a"      -> 0
"ab"     -> 0
"aba"    -> 1 ("a")
"abab"   -> 2 ("ab")
"ababc"  -> 0
"ababca" -> 1 ("a")

四、KMP匹配

public int kmp(String text, String pattern) {
    if (pattern.isEmpty()) return 0;
    int[] next = buildNext(pattern);
    
    int j = 0;
    for (int i = 0; i < text.length(); i++) {
        while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
            j = next[j - 1];
        }
        if (text.charAt(i) == pattern.charAt(j)) {
            j++;
        }
        if (j == pattern.length()) {
            return i - pattern.length() + 1;
        }
    }
    return -1;
}