字符串匹配算法在Java中的实现：从API到实战演练

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

字符串匹配算法是计算机科学中一个重要的算法类别，用于在文本中查找子字符串或模式。这些算法在各种应用中至关重要，包括文本搜索、数据挖掘和生物信息学。

字符串匹配算法根据其时间复杂度和空间复杂度进行分类。最常用的算法包括：

- **朴素字符串搜索算法**：时间复杂度为 O(mn)，其中 m 是模式的长度，n 是文本的长度。
- **KMP算法**：时间复杂度为 O(m + n)，使用预处理技术提高效率。
- **Boyer-Moore算法**：时间复杂度为 O(mn)，使用模式的字符分布信息来优化搜索。

# 2. Java中的字符串匹配算法API

Java语言提供了丰富的字符串匹配API，可以方便地进行字符串匹配操作。这些API主要分为两类：String类的字符串匹配方法和正则表达式API。

### 2.1 String类的字符串匹配方法

String类提供了多种字符串匹配方法，可以满足基本的字符串匹配需求。

#### 2.1.1 contains()方法

`contains()`方法用于检查字符串中是否包含指定的子字符串。如果包含，则返回`true`；否则，返回`false`。

String str = "Hello World";
boolean result = str.contains("World"); // true

#### 2.1.2 indexOf()和lastIndexOf()方法

`indexOf()`和`lastIndexOf()`方法用于查找指定子字符串在字符串中的第一次出现位置和最后一次出现位置。如果找不到，则返回`-1`。

String str = "Hello World World";
int firstIndex = str.indexOf("World"); // 6
int lastIndex = str.lastIndexOf("World"); // 12

#### 2.1.3 matches()方法

`matches()`方法用于检查字符串是否与指定的正则表达式模式匹配。如果匹配，则返回`true`；否则，返回`false`。

String str = "12345";
boolean result = str.matches("[0-9]+"); // true

### 2.2 正则表达式API

正则表达式是一种强大的字符串匹配语言，可以表示复杂的匹配模式。Java中提供了`Pattern`和`Matcher`类来支持正则表达式操作。

#### 2.2.1 Pattern和Matcher类

`Pattern`类用于编译正则表达式模式，而`Matcher`类用于将模式应用于字符串并执行匹配操作。

Pattern pattern = Pattern.compile("[0-9]+");
Matcher matcher = pattern.matcher("12345");
boolean result = matcher.matches(); // true

#### 2.2.2 正则表达式的语法和元字符

正则表达式使用元字符来表示通配符、量词和分组。常见的元字符包括：

* `.`：匹配任何字符
* `*`：匹配前一个字符0次或多次
* `+`：匹配前一个字符1次或多次
* `?`：匹配前一个字符0次或1次
* `[]`：匹配方括号内的任何字符
* `()`：分组

例如，正则表达式`[0-9]+`匹配一个或多个数字。

# 3.1 子字符串搜索

子字符串搜索是字符串匹配算法中最基本的任务之一，它旨在查找一个字符串（子字符串）在另一个字符串（主字符串）中的所有出现位置。子字符串搜索算法通常用于文本编辑、搜索引擎和模式识别等应用中。

#### 3.1.1 KMP算法

KMP算法（Knuth-Morris-Pratt算法）是一种高效的子字符串搜索算法，它利用预处理技术来优化搜索过程。KMP算法使用一个称为失败函数的表来记录模式字符串中每个字符匹配失败后应该跳转到的位置。

**代码块：**

public static int[] computeFailureFunction(String pattern) {
    int[] failureFunction = new int[pattern.length()];
    failureFunction[0] = 0;
    int i = 1;
    int j = 0;
    while (i < pattern.length()) {
        if (pattern.charAt(i) == pattern.charAt(j)) {
            failureFunction[i] = j + 1;
            i++;
            j++;
        } else if (j > 0) {
            j = failureFunction[j - 1];
        } else {
            failureFunction[i] = 0;
            i++;
        }
    }
    return failureFunction;
}

public static List<Integer> kmpSearch(String text, Strin