模式搜索是一种涉及搜索模式的算法，例如字符串、单词、图像等。模式搜索的复杂性因算法而异。模式搜索算法对于在较大字符串的子字符串中查找模式非常有用。
模式搜索算法的特点
- 模式搜索算法快速准确地识别熟悉的模式。
- 识别和分类不熟悉的模式。
- 即使部分隐藏也能识别模式。
- 轻松、自动地快速识别模式。
模式搜索算法的类型
朴素模式搜索算法
朴素模式搜索是模式搜索算法中最简单的方法。它检查模式的主字符串的所有字符。该算法对较小的文本很有帮助。它不需要任何预处理阶段。我们可以通过检查一次字符串来找到子字符串。它也不占用额外的空间来执行操作。
朴素模式搜索算法的时间复杂度为O(m*n)，m是模式的大小，n是主字符串的大小。
KMP算法
KMP算法用于在“文本”中查找“模式”。该算法从左到右逐个字符进行比较。但是每当出现不匹配时，它都会使用一个名为“前缀表”的预处理表来跳过匹配时的字符比较。有时前缀表也称为LPS表。
LPS表决定当发生不匹配时要跳过多少个字符进行比较。当出现不匹配时，检查模式中不匹配字符的前一个字符的LPS值。如果它是“0”，则开始将模式的第一个字符与下一个字符与文本中不匹配的字符进行比较。如果它不是“0”，则开始将索引值等于前一个字符的LPS值的字符与模式中的不匹配字符与文本中的不匹配字符进行比较。
Rabin-Karp算法
Rabin-Karp算法是一种使用哈希函数在文本中搜索/匹配模式的算法。与朴素字符串匹配算法不同，它不会在初始阶段遍历每个字符，而是过滤掉不匹配的字符，然后进行比较。
Rabin-Karp比较字符串的哈希值，而不是字符串本身。为了提高效率，文本中下一个位置的哈希值很容易从当前位置的哈希值中计算出来。
Rabin-Karp算法的工作原理
1）初步计算模式P的哈希值。
2）从字符串的开头开始迭代：
- 计算当前长度为m的子串的哈希值。
- 如果当前子串的哈希值与模式相同，则检查子串是否与模式相同。
- 如果它们相同，则将起始索引存储为有效答案。否则，继续下一个子字符串。
3）返回起始索引作为所需的答案。
Rabin-Karp算法的平均和最佳运行时间为O(n+m)，但其最坏情况时间为O(nm)。
Rabin-Karp算法的最坏情况发生在模式和文本的所有字符都相同时，txt[]的所有子串的哈希值都与pat[]的哈希值匹配。
Z算法
该算法在线性时间内找到文本中出现的所有模式。设文本长度为n，模式长度为m，则总时间为O(m+n)，具有线性空间复杂度。Z算法通过维护一个称为Z数组的辅助数组来工作。这个Z数组存储最长子串的长度，从当前索引开始，也是它的前缀。
Aho-Corasick算法
Aho-Corasick算法在O(n+m+z)时间内找到所有单词，其中z是文本中单词出现的总数。Aho–Corasick字符串匹配算法构成了原始Unix命令“fgrep”的基础。
预处理：将arr[]中的所有单词构建一个自动机自动机主要有三个功能：
转到：此函数简单地跟随arr[]中所有单词的Trie边。
它表示为二维数组g[][]，我们在其中存储当前状态和字符的下一个状态。
失败：该函数存储当前字符在Trie中没有边时所跟随的所有边。
它表示为一维数组f[]，我们在其中存储当前状态的下一个状态。
输出：存储以当前状态结束的所有单词的索引。
它表示为一维数组o[]，我们将所有匹配词的索引存储为当前状态的位图。
匹配：在构建的自动机上遍历给定的文本以找到所有匹配的单词。
时间复杂度O(n+l+z)，其中“n”是文本的长度，“l”是关键字的长度，“z”是匹配的数量。辅助空间O(l*q)，其中“q”是字母表的长度，因为这是一个节点可以拥有的最大子节点数。
