前言

在字符串处理领域，字符串匹配是一个常见且重要的问题。给定一个文本串text和一个模式串pattern，我们希望找到模式串在文本串中第一次出现的位置。

最朴素的字符串匹配算法是暴力匹配（Brute Force），其时间复杂度为 $O(n\ast m)$，其中 n 和 m 分别是文本串和模式串的长度。当文本串和模式串都很长时，这种算法的效率就显得很低。

为了提高匹配效率，其中 KMP 算法（Knuth-Morris-Pratt 算法）是一种经典且高效的算法，其时间复杂度为 O (n+m)。本文我将介绍 KMP 算法的原理、实现和应用。

KMP 算法的实现

KMP 算法的实现主要分为两部分：计算 LPS 数组和利用 LPS 数组进行匹配。

计算 LPS 数组

计算 LPS 数组的核心思想是利用已经计算出的 LPS 值来加速后续 LPS 值的计算。具体步骤如下：

初始化 LPS 数组，长度为模式串的长度，初始值都为 0

使用两个指针len和i，其中len表示当前最长相等前缀和后缀的长度，初始值为 0；i从 1 开始遍历模式串

如果当前字符与len位置的字符相等，则len加 1，lps[i]设为len，然后i加 1

如果不相等，则将len回溯到lps[len-1]，继续比较，直到len为 0 或者找到匹配

下面是三种语言实现的 KMP 算法代码：

Java 实现

public class KMP {
    public static int kmpSearch(String text, String pattern) {
        if (text == null || pattern == null || pattern.length() == 0) {
            return 0;
        }
        int n = text.length();
        int m = pattern.length();
        if (m > n) {
            return -1;
        }
        
        int[] lps = computeLPSArray(pattern);
        int i = 0; // 文本指针
        int j = 0; // 模式指针
        
        while (i < n) {
            if (pattern.charAt(j) == text.charAt(i)) {
                j++;
                i++;
            }
            
            if (j == m) {
                return i - j; // 找到匹配，返回起始索引
            } else if (i < n && pattern.charAt(j) != text.charAt(i)) {
                // 不匹配时，调整j的位置
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        
        return -1; // 未找到匹配
    }
    
    private static int[] computeLPSArray(String pattern) {
        int m = pattern.length();
        int[] lps = new int[m];
        int len = 0;
        int i = 1;
        lps[0] = 0; // lps[0]总是0
        
        while (i < m) {
            if (pattern.charAt(i) == pattern.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        
        return lps;
    }
    
    public static void main(String[] args) {
        String text = "ABABDABACDABABCABAB";
        String pattern = "ABABCABAB";
        int index = kmpSearch(text, pattern);
        if (index != -1) {
            System.out.println("模式串在文本中的起始索引是: " + index);
        } else {
            System.out.println("未找到匹配的模式串");
        }
    }
}

C++ 实现

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

vector<int> computeLPSArray(const string& pattern) {
    int m = pattern.length();
    vector<int> lps(m, 0);
    int len = 0;
    int i = 1;
    
    while (i < m) {
        if (pattern[i] == pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    
    return lps;
}

int kmpSearch(const string& text, const string& pattern) {
    int n = text.length();
    int m = pattern.length();
    
    if (m == 0) {
        return 0;
    }
    
    vector<int> lps = computeLPSArray(pattern);
    int i = 0; // 文本指针
    int j = 0; // 模式指针
    
    while (i < n) {
        if (pattern[j] == text[i]) {
            j++;
            i++;
        }
        
        if (j == m) {
            return i - j; // 找到匹配，返回起始索引
        } else if (i < n && pattern[j] != text[i]) {
            // 不匹配时，调整j的位置
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
    
    return -1; // 未找到匹配
}

int main() {
    string text = "ABABDABACDABABCABAB";
    string pattern = "ABABCABAB";
    int index = kmpSearch(text, pattern);
    
    if (index != -1) {
        cout << "模式串在文本中的起始索引是: " << index << endl;
    } else {
        cout << "未找到匹配的模式串" << endl;
    }
    
    return 0;
}

Python 实现

def compute_lps_array(pattern):
    m = len(pattern)
    lps = [0] * m
    length = 0
    i = 1
    
    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
    
    return lps

def kmp_search(text, pattern):
    n = len(text)
    m = len(pattern)
    
    if m == 0:
        return 0
    
    lps = compute_lps_array(pattern)
    i = 0  # 文本指针
    j = 0  # 模式指针
    
    while i < n:
        if pattern[j] == text[i]:
            j += 1
            i += 1
        
        if j == m:
            return i - j  # 找到匹配，返回起始索引
        elif i < n and pattern[j] != text[i]:
            # 不匹配时，调整j的位置
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    
    return -1  # 未找到匹配

if __name__ == "__main__":
    text = "ABABDABACDABABCABAB"
    pattern = "ABABCABAB"
    index = kmp_search(text, pattern)
    
    if index != -1:
        print(f"模式串在文本中的起始索引是: {index}")
    else:
        print("未找到匹配的模式串")

复杂度分析

时间复杂度：计算 LPS 数组的时间复杂度为 O (m)，其中 m 是模式串的长度；匹配过程的时间复杂度为 O (n)，其中 n 是文本串的长度。因此，KMP 算法的总时间复杂度为 O (n+m)。

空间复杂度：KMP 算法需要额外的 O (m) 空间来存储 LPS 数组。

应用场景

单次字符串匹配：在一个较长的文本中查找一个模式串的出现位置。

多次字符串匹配：在一个较长的文本中查找多个模式串的出现位置，可以对每个模式串分别使用 KMP 算法。

生物信息学：在 DNA 序列中查找特定的基因片段。

文本编辑器：在文本编辑器中实现查找和替换功能。

搜索引擎：在网页中搜索关键词。

总结

KMP 算法是一种高效的字符串匹配算法，通过预处理模式串构建 LPS 数组，避免了在匹配过程中的不必要回溯，从而将时间复杂度从 $O(n\ast m)$ 降低到 $O(n+m)$。希望你在看完本文后能够更好地理解和掌握 KMP 算法，提高字符串处理的效率。

That’s all, thanks for reading!
创作不易，点赞鼓励；
知识无价，收藏备用；
持续精彩，关注不错过！