模式搜索算法用于从另一个更大的字符串中查找模式或子字符串。存在不同的算法。设计此类算法的主要目标是降低时间复杂度。对于较长的文本，传统方法可能需要大量时间才能完成模式搜索任务。在这里，我们将看到不同的算法以获得更好的模式匹配性能。在本节中，我们将介绍以下内容：Aho-Corasick 算法、字谜模式搜索、坏字符启发式、Boyer Moore 算法、有限自动机的有效构建、Kasai 算法、Knuth-Morris-Pratt 算法、Manacher 算法、朴素模式搜索、Rabin-Karp ... 阅读更多

此算法命名为 Z 算法，因为在此算法中，我们需要创建一个 Z 数组。Z 数组的大小与文本大小相同。此数组用于存储从主字符串的当前字符开始的最长可能子字符串的长度。首先，模式和主文本与文本和模式中不存在的特殊符号连接。如果 P 是模式，T 是主文本，则连接后，它将是 P$T（假设 $ 不存在于 P ... 阅读更多

从文本中，我们可以生成所有后缀以形成树结构。我们知道文本中出现的每个模式都必须是文本中一个可能后缀的前缀。通过构建所有后缀的 Trie 树，我们可以在线性时间内找到任何子字符串。每个后缀都以字符串终止符号结尾。从每个节点，如果存在任何路径，它将向前移动，否则返回该模式未找到。对于此算法，时间复杂度为 O(m+k)，其中 m 是字符串的长度，k 是模式在 ... 阅读更多

从给定字符串中，我们可以获得所有可能的后缀。按字典顺序对后缀进行排序后，我们可以得到后缀数组。后缀数组也可以使用后缀树形成。通过使用后缀树的 DFS 遍历，我们可以得到后缀数组。后缀数组有助于在线性时间内查找后缀。我们还可以使用类似二分搜索的过程，使用后缀数组查找子字符串。时间复杂度为 O(m log n)输入和输出输入：主字符串：“BANANA”，模式：“NAN”输出：模式在位置 2 处找到算法fillSuffixArray (text, suffArray)输入：主字符串输出：后缀数组开始 n := text Length ... 阅读更多

Rabin-Karp 是一种另一种模式搜索算法，可以更有效地查找模式。它也通过逐个移动窗口来检查模式，但并非在所有情况下都检查所有字符，而是查找哈希值。当哈希值匹配时，它才会尝试检查每个字符。此过程使算法更有效。时间复杂度为 O(m+n)，但对于最坏情况，它为 O(mn)。输入和输出输入：主字符串：“ABAAABCDBBABCDDEBCABC”，模式“ABC”输出：模式在位置 4 处找到模式在位置 10 处找到模式在位置 18 处找到算法rabinKarpSearch(text, pattern, prime)输入 - 主 ... 阅读更多

朴素模式搜索是在其他模式搜索算法中最简单的方法。它检查主字符串的所有字符与模式。此算法适用于较小的文本。它不需要任何预处理阶段。我们可以通过检查字符串一次来找到子字符串。它也不占用额外的空间来执行操作。朴素模式搜索方法的时间复杂度为 O(m*n)。m 是模式的大小，n 是主字符串的大小。输入和输出输入：主字符串：“ABAAABCDBBABCDDEBCABC”，模式：“ABC”输出：模式在位置 4 处找到模式在 ... 阅读更多

要从字符串中找到最长的回文子字符串，我们可以使用 Manacher 算法。通过选择每个字符，我们将尝试使用左右指针查找是否存在任何回文。还有一个数组用于存储信息，从这些信息中我们可以很容易地找到回文有多长。对于每个字符，数组将存储信息。遍历整个字符串后，我们可以从创建的数组中找到最长的回文子序列。此算法的时间复杂度为 O(n)。输入和输出输入：字符串：“levelup”输出：最长回文是：level算法longestPalindrome(text)输入 - 要查找最长回文的文本输出 - ... 阅读更多

Kasai 算法用于从后缀数组中获取最长公共前缀 (LCP) 数组。首先找到后缀数组。之后，Kasai 算法获取后缀数组列表以查找 LCP。对于 LCP 数组，它需要 O(m log n)，其中 m 是模式长度，n 是文本的长度。Kasai 算法需要 O(n) 来在主字符串中搜索模式。输入和输出输入：主字符串：“banana”输出：后缀数组：5 3 1 0 4 2 公共前缀数组：1 3 0 0 2 0算法buildSuffixArray(text)输入：主字符串输出：后缀数组，构建 ... 阅读更多

通过构建有限自动机，我们可以简单地执行文本中的模式搜索。首先，我们必须填充一个二维数组以创建有限自动机的转换表。创建表后，搜索过程很简单。从自动机的第一个状态开始，当我们到达最终状态时，这意味着在字符串中找到了模式。对于有限自动机的构建，时间复杂度为 O(M*K)，M 是模式长度，K 是不同字符的数量。主模式搜索的复杂度为 O(n)。输入和输出输入：主字符串： ... 阅读更多

坏字符启发式方法是 Boyer Moore 算法的一种方法。另一种方法是好后缀启发式。在这种方法中，我们将尝试找到一个坏字符，这意味着主字符串的一个字符，它与模式不匹配。当发生不匹配时，我们将移动整个模式，直到不匹配变成匹配，否则，模式将移过坏字符。这里时间复杂度对于最佳情况为 O(m/n)，对于最坏情况为 O(mn)，其中 n 是文本的长度，m 是模式的长度。输入和 ... 阅读更多