模式搜索算法用于在一个较大的字符串中查找模式或子字符串。存在不同的算法。设计这类算法的主要目标是降低时间复杂度。对于较长的文本，传统方法可能需要很长时间才能完成模式搜索任务。在这里，我们将看到不同的算法，以获得更好的模式匹配性能。在本节中，我们将介绍：Aho-Corasick算法、Anagram模式搜索、坏字符启发式算法、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是模式长度。输入和……阅读更多