本文介绍字符串匹配算法，在开始前，先讲两个常用的概念。
- 主串: 被查找的字符串
- 模式串：要操作的字符串
- 多模式串匹配算法：在多个模式串中匹配一个文本串的算法，比如敏感此过滤。
1. BF 算法
Brute Force，暴力匹配算法，也叫朴素匹配算法。
思路：在主串中，检查起始位置分别是 0、1、2…n-m且长度为 m 的 n-m+1 个子串，看有没有跟模式串匹配的。简单说就是把主串的所有子串挨个儿跟模式串比较。
public class BruteForce {
public static int search(String text, String pattern) {
int n = text.length();
int m = pattern.length();
for (int i = 0; i <= n - m; i++) {
int j;
for (j = 0; j < m; j++) {
if (text.charAt(i+j) != pattern.charAt(j)) {
break;
}
}
if (j == m) {
return i;
}
}
return -1;
}
}
时间复杂度：理论上的最坏情况时间复杂度是 O(n*m)，但是大部分情况下，算法执行效率要比这个高很多，所以在文本比较小的情况下，一般来说这就足够简单，够用了。
BK 算法
BK全称叫Rabin-Karp算法，两位发明者Rabin和Karp的名字来命名的。我们看BF效率很低的一点：每个子串都要和模式串的每个字符比较。如果把模式串hash为一个数字，虽然需每个子串进行hash，但模式串一次hash后就可以保存下来，和字符hash比较，减少了比较的次数。
于是，BK算法的重点就是这个hash算法，而hash算法的主要关注效率和冲突解决办法。
Rabin-Karp算法的哈希函数采用的是基于进制的思想，这是这个算法的核心。具体来说，它将字符串看作是一个进制为d的数。
比如要处理的字符串只包含 a～z 这 26 个小写字母，那我们就用二十六进制来表示一个字符串。我们把 a～z 这 26 个字符映射到 0～25 这 26 个数字，0就表示a，1表示b…z表示25。
在十进制的表示法中，一个数字的值是通过下面的方式计算出来的。对应到二十六进制，一个包含 a 到 z 这 26 个字符的字符串，计算哈希的时候，我们只需要把进位从 10 改成 26 就可以。 ![[Pasted image 20230408190658.png]]
S = s[0] * d^(n-1) + s[1] * d^(n-2) + ... + s[n-2] * d + s[n-1]
其中，S是字符串的哈希值，s[i]是字符串中的第i个字符，n是字符串的长度，d是进制常数。
这样，计算是非常快的，还可以进一步优化速度。如果在cabejifs种查eji，如上：
hash(cab)= c * 26 ^ 2 + a * 26^1 +b * 26^0
hash(abe)= a * 26^2 + b * 26^1 +c = 26 *（a * 26^1 +b * 26^0） + e=
(hash(cab) - c * d^(m-1)) * d + e
这个公式可以称为滚动哈希，避免每次重新计算字符串的哈希值，而是通过对先前的哈希值进行简单的修改，来得到新的哈希值。另外还可以把d的n次方先计算好存起来直接使用，省去了计算的时间。
整个 RK 算法包含两部分，计算子串哈希值和模式串哈希值与子串哈希值之间的比较。第一部分可以通过设计特殊的哈希算法，只需要扫描一遍主串就能计算出 所有子串的哈希值了，所以这部分的时间复杂度是 O(n)。RK算法整体的时间复杂度就是O(n)。
为了避免hash值过大，需要哈希值对一个大质数p取模得到最终的哈希值：
H(S) = S mod p
解决hash冲突的方法也很简单，当我们发现一个子串的哈希值跟模式串的哈希值相等的时候，再对比一下子串和模式串本身就好了。
适用场景： Rabin-Karp算法可以用于解决字符串匹配问题，特别是当模式串比较短时效果较好。因此可以应用于文本编辑器、字符串搜索、数据压缩等领域。 核心思想：hash–>进制滚动hash–>存储d的n次方优化滚动hash
BM（Boyer-Moore）
RK算法虽然很高效了，但还是要处理主串的每个字符。BM算法（Boyer-Moore算法）是一种用于字符串匹配的高效算法，它能够在较短的时间内搜索出大型文本中的某个模式串。
该算法的基本思想是从模式串的末尾开始匹配，通过预处理模式串，可以利用好已经匹配过的信息，从而跳过一些不必要的匹配操作。具体而言，BM算法包括两个主要部分：坏字符规则和好后缀规则。
坏字符 从模式串的末尾往前倒着匹配，当我们发现某个字符没法匹配的时候。我们把这个没有 匹配的字符叫作坏字符（主串中的字符），然后查找这个坏字符在模式串中出现的最后位置，并根据这个位置将模式串向后移动一定的距离，以此来避免重复比较已经匹配的字符。 ![[Pasted image 20230408213112.png]] 如上图，按BF算法，如果abc和abd比对到c和d不匹配，移动一位用bca和abd继续比较，但实际上c压根没在abd里面，前面的比对是多余的，从c+1位aca开始比对就好了，如下图。 ![[Pasted image 20230408213147.png]] 但如果坏字符在模式串里面，就不能移动到坏字符+1的位置。比如对上图进行第二次比对，a就是坏字符，整个模式串都移动到a的下一个位置并不对。需要把模式串种坏字符串最后出现的位置和坏字符串对齐。
通过如上方式可以跳过很多无需查找的字符。但在模式串中顺序遍历查找，这样就会比较低效。于是，散列表派上用场。
常规：出现坏字符。从模式串m-1开始比对，返回对应下标。如果坏字符不在模式串种，需要遍历m次。 散列表：初始化一个数组(要看字符集大小)，遍历模式串，字符hash作为数组下标，数组值为字符在模式串的位置。出现多次的字符，数组保存的是最后出现的位置。坏字符可以在hash表种快速找到数组下标。
private static final int SIZE = 256;
// 预处理坏字符表，这里256，只能处理ascii这个字符集
private void generateBC(char[] b, int m, int[] bc) {
for (int i = 0; i < SIZE; ++i) {
bc[i] = -1; // 初始化 bc
}
for (int i = 0; i < m; ++i) {
int ascii = (int)b[i]; // 计算 b[i] 的 ASCII 值
bc[ascii] = i;
}
}
public int bm(char[] a, int n, char[] b, int m) {
int[] bc = new int[SIZE]; // 记录模式串中每个字符最后出现的位置
generateBC(b, m, bc); // 构建坏字符哈希表
int i = 0; // i 表示主串与模式串对齐的第一个字符
while (i <= n - m) {
int j;
for (j = m - 1; j >= 0; --j) {
// 模式串从后往前匹配
if (a[i+j] != b[j]) break; // 坏字符对应模式串中的下标是 j
}
if (j < 0) {
return i; // 匹配成功，返回主串与模式串第一个匹配的字符的位置
} // 这里等同于将模式串往后滑动 j-bc[(int)a[i+j]] 位
i = i + (j - bc[(int)a[i+j]]);
}
return -1;
}
好后缀 好后缀规则指的是，当匹配过程中遇到一个完全匹配的子串时，将其称为“好后缀”，然后查找这个好后缀在模式串中出现的最后位置，并根据这个位置将模式串向后移动一定的距离，以此来利用好已经匹配的信息。
// TODO 举例详细
通过组合坏字符规则和好后缀规则，BM算法能够在搜索文本中匹配模式串的过程中，极大地提高匹配效率。
实现步骤：
- 预处理坏字符表和好后缀表，其中坏字符表记录模式串中每个字符最后出现的位置，好后缀表记录每个后缀的最长匹配好后缀长度。
- 在文本串中从前往后匹配模式串，每次匹配失败时根据坏字符表和好后缀表进行移动。
- 移动步长为坏字符规则和好后缀规则中计算得到的最大值。
- 若匹配成功，则返回匹配的起始位置；否则返回-1表示文本串中没有找到匹配的子串。
public class BoyerMoore {
//预处理坏字符表，返回一个长度为256的整型数组，每个元素代表对应的字符在模式串中最后出现的位置
private static int[] generateBadCharTable(char[] pattern) {
int[] badCharTable = new int[256];
Arrays.fill(badCharTable, -1);
for (int i = 0; i < pattern.length; i++) {
badCharTable[pattern[i]] = i;
}
return badCharTable;
}
//计算模式串的后缀数组，返回一个长度为m+1的整型数组，suffix[i]表示模式串的后缀i的长度
private static int[] generateSuffixTable(char[] pattern) {
int m = pattern.length;
int[] suffixTable = new int[m + 1];
Arrays.fill(suffixTable, m);
int[] prefix = new int[m];
Arrays.fill(prefix, -1);
for (int i = 0; i < m; i++) {
int j = i;
int k = 0;
while (j >= 0 && pattern[j] == pattern[m - 1 - k]) {
j--;
k++;
prefix[k] = j + 1;
}
if (j == -1) {
suffixTable[k] = m - 1 - i;
}
}
for (int i = 0; i < m - 1; i++) {
int k = suffixTable[m - 1 - i];
if (prefix[k] != -1) {
suffixTable[m - 1 - prefix[k]] = k - prefix[k];
}
}
return suffixTable;
}
//使用Boyer-Moore算法在文本串text中查找模式串pattern，并返回匹配的起始位置，若未找到则返回-1
public static int search(char[] text, char[] pattern) {
int n = text.length;
int m = pattern.length;
if (m == 0) {
return 0;
}
int[] badCharTable = generateBadCharTable(pattern);
int[] suffixTable = generateSuffixTable(pattern);
int i = m - 1;
while (i < n) {
int j = m - 1;
while (j >= 0 && text[i] == pattern[j]) {
i--;
j--;
}
if (j == -1) {
return i + 1;
}
int badChar = badCharTable[text[i]];
int suffix = suffixTable[j + 1];
i += Math.max(badChar - j, suffix);
}
return -1;
}
//测试代码
public static void main(String[] args) {
String text = "ABCABCDABABCDABCDABDE";
String pattern = "ABCDABD";
int index = search(text.toCharArray(), pattern.toCharArray());
if (index != -1) {
System.out.println("Pattern found at index " + index);
} else {
System.out.println("Pattern not found");
}
}
}
KMP算法
BM 算法虽然比较复杂且难以理解，但它是工程中非常常用的高效字符串匹配算法之一。有统计数据表明，BM 算法是最高效、最常用的字符串匹配算法之一。然而，在所有的字符串匹配算法中，如果要提到最知名的一种，那就非 KMP 算法莫属了。很多时候提到字符串匹配，我们首先想到的就是 KMP 算法。
// TODO
Trie树
当我们需要在大量字符串集合中查找某个字符串时，常规的线性搜索算法的时间复杂度会随着字符串集合大小的增加而急剧增加，效率非常低。Trie 树（字典树）是一种用于快速搜索字符串的数据结构，其时间复杂度为 O(k)，其中 k 是待查找字符串的长度。Trie 树可以高效地存储和检索大量的字符串，因此在文本搜索、自动补全、拼写检查等场景中得到了广泛应用。
什么是Trie树？
Trie 树，也叫字典树、前缀树，是一种多叉树结构，用于处理字符串集合的查找和统计。它将每个字符串作为一条路径存储在树中，从根节点到叶子节点的路径所组成的字符串就是对应的字符串。Trie 树的根节点代表空字符串，每个非空字符串都从根节点开始，沿着相应的边到达叶子节点。如果两个字符串有相同的前缀，它们会共享同一个前缀路径，从而节省空间。
下图展示了一个简单的 Trie 树：
在上面的 Trie 树中，我们可以看到有 5 个字符串被插入，即 “the”、“a”、“there”、“answer” 和 “any”。在 Trie 树中，每个节点包含多个指针，每个指针代表一个字符。从根节点开始，通过遍历字符指针，可以从 Trie 树中检索出对应的字符串。例如，检索字符串 “there” 的过程如下：
- 从根节点开始，遍历字符指针 “t”，到达节点 1。
- 继续遍历字符指针 “h”，到达节点 2。
- 继续遍历字符指针 “e”，到达节点 4。
- 继续遍历字符指针 “r”，到达节点 5。
- 继续遍历字符指针 “e”，到达节点 6。
- 检查节点 6 是否是叶子节点，如果是，说明字符串 “there” 存在于 Trie 树中。
在上述过程中，我们一路走到叶子节点 6，说明字符串 “there” 存在于 Trie 树中。Trie 树的检索过程时间复杂度为 O(k)，其中 k 是待查找字符串的长度，因此非常高效。
Trie树的Java实现
下面是使用 Java 实现的 Trie 树的基本代码：
class TrieNode {
private TrieNode[] children;
private boolean isEnd;
public TrieNode() {
children = new TrieNode[26];
isEnd = false;
}
适用：字符串查找和匹配，前缀匹配，自动完成和提示，字符串排序 不适用：对于稀疏的字符串集合，对于长字符串集合，对于动态数据集合。
AC自动机
核心思想： AC自动机算法的核心思想是在Trie树的基础上构建DFA（Deterministic Finite Automaton）有限状态自动机，并且使用BFS（Breadth First Search）算法进行匹配过程。AC自动机算法的基本思想是将多个模式串构建成一颗Trie树，并使用一些特殊的技巧将其转化为DFA自动机，使得匹配过程可以在O(n)的时间复杂度内完成。
核心步骤：
- 构建Trie树：将所有模式串构建成一颗Trie树，并标记每个Trie节点所对应的模式串集合。
- 构建DFA自动机：通过遍历Trie树节点，并且将节点之间的关系转化为DFA自动机状态转移函数。
- 匹配过程：在文本串中进行模式匹配，当匹配到某个节点时，根据节点的转移函数转移到下一个节点，直到到达终止状态，输出匹配结果。
import java.util.*;
public class AhoCorasick {
private static class Node {
Map<Character, Node> children = new HashMap<>();
List<String> matches = new ArrayList<>();
Node fail;
void addMatch(String s) {
matches.add(s);
}
}
private final Node root;
public AhoCorasick(List<String> patterns) {
root = new Node();
// 构建Trie树
for (String pattern : patterns) {
Node node = root;
for (char c : pattern.toCharArray()) {
node.children.putIfAbsent(c, new Node());
node = node.children.get(c);
}
node.addMatch(pattern);
}
// 构建DFA自动机
Queue<Node> queue = new LinkedList<>();
for (Node node : root.children.values()) {
queue.offer(node);
node.fail = root;
}
while (!queue.isEmpty()) {
Node node = queue.poll();
for (Map.Entry<Character, Node> entry : node.children.entrySet()) {
char c = entry.getKey();
Node child = entry.getValue();
queue.offer(child);
Node fail = node.fail;
while (fail != root && !fail.children.containsKey(c)) {
fail = fail.fail;
}
child.fail = fail.children.getOrDefault(c, root);
child.matches.addAll(child.fail.matches);
}
}
}
public List<Integer> search(String s) {
List<Integer> result = new ArrayList<>();
引用：