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

从给定的字符串中，我们可以获得所有可能的后缀。按字典序对后缀排序后，我们可以得到后缀数组。后缀数组也可以使用后缀树来构建。使用后缀树的深度优先搜索遍历，我们可以得到后缀数组。后缀数组有助于在线性时间内查找后缀。我们还可以使用类似二分查找的方法，使用后缀数组查找子串。时间复杂度为 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 是模式的长度。输入和… 阅读更多

回文基本上是给定字符串或模式的所有排列。这种模式搜索算法略有不同。在这种情况下，不仅搜索确切的模式，还搜索文本中给定模式的所有可能排列。为了解决这个问题，我们将整个文本划分为几个长度与模式相同的窗口。然后计算并存储模式中每个字符的计数。对于每个窗口，我们还尝试查找计数数组，然后检查它们是否匹配。回文模式搜索算法的时间复杂度为 O(n)。输入… 阅读更多

该算法有助于查找所有给定关键词的所有出现位置。这是一种字典匹配算法。它使用包含所有关键词的树结构。构建树之后，它尝试将树转换为自动机，以便线性时间内进行搜索。Aho-Corasick算法共有三个阶段：跳转(Go-to)、失败(Failure)和输出(Output)。在跳转阶段，它使用所有关键词构建树。在下一个阶段，即失败阶段，它尝试查找向后转换以获得某些关键词的适当后缀。在……阅读更多