Lua字符串算法专家：KMP与Boyer-Moore算法详解

# 1. 字符串匹配基础与算法概述

## 1.1 字符串匹配的重要性
在信息检索、文本编辑、网络安全等多个IT领域，字符串匹配是一种基本且核心的操作。它涉及到从一段文本中找到与特定模式（pattern）相匹配的所有子串。简单地说，它帮助我们识别模式在文本中的存在以及它们出现的位置。

## 1.2 字符串匹配算法的分类
字符串匹配算法可以大致分为两类：暴力匹配算法和高效算法。暴力匹配算法通过逐个字符比较来寻找匹配，尽管直观但效率较低。高效算法如KMP、Boyer-Moore等，则通过预处理模式串或文本串来跳过不必要的比较，从而提高了匹配的效率。

## 1.3 暴力匹配算法的介绍
最简单的字符串匹配方法是暴力匹配算法。它的基本思想是：对于文本中的每一个字符作为起点，依次与模式串中的字符进行比较。如果在某一点上字符不匹配，则文本串的指针右移一位，模式串重新从头开始匹配。这种方法的时间复杂度为O(n*m)，其中n是文本串长度，m是模式串长度。显然，当文本串和模式串都较长时，暴力匹配将变得非常低效。

def naive_match(text, pattern):
    n, m = len(text), len(pattern)
    for i in range(n - m + 1):
        j = 0
        while j < m and text[i + j] == pattern[j]:
            j += 1
        if j == m:
            return i  # 匹配成功，返回模式串在文本串中的起始位置
    return -1  # 匹配失败

暴力匹配算法虽然简单，但它的高时间复杂度限制了它的应用范围。因此，研究和应用更高效的算法就显得尤为重要。接下来的章节将详细介绍KMP算法，这是一种改进的字符串匹配算法，能够有效地减少不必要的比较次数，从而提高效率。

# 2. KMP算法详解

## 2.1 KMP算法的理论基础

### 2.1.1 字符串匹配问题的复杂性

字符串匹配是计算机科学中的一个经典问题，它涉及到在一个主字符串（通常称为文本）中查找与另一个模式字符串匹配的子串。这个看似简单的任务，在没有适当算法的情况下，可能会需要大量的计算。

最直接的方法是尝试所有可能的对齐方式，这种方法被称为暴力匹配算法。对于长度为n的文本和长度为m的模式，暴力算法的时间复杂度为O(nm)，在处理大型数据集时效率低下。

### 2.1.2 KMP算法的核心思想

KMP算法（Knuth-Morris-Pratt）是由Donald Knuth、Vaughan Pratt和James H. Morris发明的一种高效的字符串匹配算法，它的主要贡献在于减少不必要的比较次数。算法的核心在于一个称为“部分匹配表”（也称为“最长公共前后缀”表）的数据结构，它记录了模式自身与前缀的最长匹配长度。

当在文本中进行搜索时，如果发生不匹配，KMP算法利用部分匹配表的信息，将模式字符串相对于文本适当地向右移动，从而避免从头开始比较，大大提高了搜索效率。其时间复杂度为O(n)，因此在长字符串的模式匹配中具有显著优势。

## 2.2 KMP算法的实现过程

### 2.2.1 部分匹配表（Partial Match Table）的构建

部分匹配表是KMP算法的核心，它的构建基于以下想法：给定一个模式字符串，我们考虑其所有前缀，记录每个前缀的最长相等前后缀的长度（不包括前缀本身）。这些信息可以组织成一个表，例如对于模式字符串 "ABCDABD"，其部分匹配表如下：

A  B  C  D  A  B  D
0  0  0  0  1  2  0

表中的每个数字表示模式字符串在当前位置之前的子串的最长公共前后缀的长度。

### 2.2.2 KMP搜索算法的步骤

KMP搜索算法的步骤如下：

1. 初始化两个指针：一个指向文本的起始位置（textIndex），另一个指向模式的起始位置（patternIndex）。
2. 遍历文本字符串，将当前字符与模式字符串的对应字符比较。
3. 如果字符匹配，两个指针都向前移动；如果不匹配，则根据部分匹配表移动patternIndex，并保持textIndex不变。
4. 如果patternIndex达到模式字符串的长度，则表示找到了一个匹配，更新匹配结果，并根据部分匹配表调整patternIndex，继续搜索下一个匹配。
5. 重复步骤2-4直到文本字符串结束。

## 2.3 KMP算法的代码实例与分析

### 2.3.1 Lua中的KMP实现

下面是KMP算法在Lua语言中的一个实现示例：

function buildPartialMatchTable(pattern)
    local m = #pattern
    local lps = table.create(m, 0) -- Longest Prefix Suffix
    local len = 0 -- Length of the previous longest prefix suffix
    local i = 1

    while i < m do
        if pattern:sub(i, i) == pattern:sub(len + 1, len + 1) then
            len = len + 1
            lps[i] = len
            i = i + 1
        else
            if len ~= 0 then
                len = lps[len]
            else
                lps[i] = 0
                i = i + 1
            end
        end
    end
    return lps
end

function kmpSearch(text, pattern)
    local n = #text
    local m = #pattern
    local lps = buildPartialMatchTable(pattern)
    local i = 1
    local j = 1

    while i <= n do
        if pattern:sub(j, j) == text:sub(i, i) then
            i = i + 1
            j = j + 1
        end

        if j == m then
            print("Found pattern at index " .. (i - j))
            j = lps[j - 1]
        elseif i < n and pattern:sub(j, j) ~= text:sub(i, i) then
            if j ~= 1 then
                j = lps[j - 1]
            else
                i = i + 1
            end
        end
    end
end

-- Example usage:
kmpSearch("ABABDABACDABABCABAB", "ABABCABAB")

### 2.3.2 KMP算法的时间复杂度分析

KMP算法的时间复杂度由两部分组成：构建部分匹配表的时间和搜索过程的时间。构建部分匹配表的过程只依赖于模式字符串，因此其时间复杂度为O(m)，其中m是模式字符串的长度。

在搜索过程中，KMP算法避免了不必要的比较，每次比较不匹配后，模式字符串至少向前移动一位，因此，其在最坏情况下也可以达到O(n)的时间复杂度，其中n是文本字符串的长度。因此，总体的时间复杂度为O(n+m)。

# 3. Boyer-Moore算法详解

## 3.1 Boyer-Moore算法的理论基础

### 3.1.1 坏字符规则

Boyer-Moore算法是一种高效的字符串匹配算法，特别适用于模式串较短，而待匹配的文本串较长的情况。其主要思想是通过一种启发式的方法从待匹配文本串的末尾开始，向左进行匹配。其核心特性是利用已知的模式串信息来跳过尽可能多的文本串字符。

在Boyer-Moore算法中，“坏字符规则”是一种重要机制。坏字符指的是在当前匹配过程中，文本串中当前考虑的字符，在模式串中没有匹配的情况。这时，算法将模式串向右移动一段距离，直到坏字符能够和模式串中的某个字符对齐。移动的距离是通过查找一个预设的坏字符表来决定的。坏字符表存储了模式串中每个字符最后出现的位置。

### 3.1.2 好后缀规则

除了坏字符规则之外，Boyer-Moore算法还引入了“好后缀规则”。好后缀是指文本串中的一个子串，它与模式串的末尾部分相匹配。如果在文本串中找到一个与模式串后缀匹配的好后缀，但该后缀的前缀无法匹配，那么同样需要移动模式串，并且移动的距离由好后缀决定。

好后缀规则通过预设的好后缀表来确定模式串需要向右移动的距离。在实现时，好后缀表需要和坏字符表进行一些整合，以处理好后缀和坏字符同时出现的情况。

## 3.2 Boyer-Moore算法的实现过程

### 3.2.1 坏字符规则的实现细节

实现坏字符规则时，首先需要构建一个坏字符表，这个表是一个数组，其索引代表所有可能的字符，而数组的值代表对应字符在模式串中最右出现的位置。如果字符不在模式串中出现，则对应值为-1。表的初始化较为耗时，但之后的查询操作速度很快。

伪代码如下：

function build_bad_character_table(pattern)
    bad_character_table = create an array of size σ, where σ is the size of the character set
    for each character c in the character set
        last_occurrence = find the last occurrence of c in the pattern, or -1 if not found
        bad_cha