为了在一个字符串中找到最长的回文子串，我们可以使用 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。在 Go-to 阶段，它使用所有关键字创建树。在下一阶段或 Failure 阶段，它尝试找到向后转换以获得某些关键字的适当后缀。在... 阅读更多

它与之前的算法类似。唯一的区别是，图 G(V, E) 由邻接表表示。邻接表表示的时间复杂度为 O(E log V)。输入和输出输入：成本矩阵：输出：边：A--B 和成本：1 边：B--E 和成本：2 边：A--C 和成本：3 边：A--D 和成本：4 边：E--F 和成本：2 边：F--G 和成本：3 总成本：15算法prims(g: Graph, start)输入 - 图 g 和名为“start”的种子顶点输出 - 添加边后的树开始 创建两个集合 B、N 将起始节点添加到 B ... 阅读更多

给定一个连通图 G(V, E)，并且给出了每条边的权重或成本。Prim 算法将从图 G 中找到最小生成树。这是一种增量树方法。该算法需要一个种子值来启动树。种子顶点被扩展以形成整个树。该问题将使用两个集合来解决。一个集合保存已选择的节点，另一个集合保存尚未考虑的项目。从种子顶点开始，它根据最小边成本获取相邻顶点，从而通过... 阅读更多

给定到达时间和离开时间的列表。现在的问题是找到铁路所需的最小站台数量，因为没有火车等待。通过对所有时间进行排序，我们可以很容易地找到解决方案，这将很容易跟踪火车何时到达但未离开车站。这个问题的时间复杂度为 O(n Log n)。输入和输出输入：到达时间和离开时间的列表。到达：{900, 940, 950, 1100, 1500, 1800} 离开：{910, 1200, 1120, 1130, 1900, 2000} 输出：所需的最小站台数量：3算法minPlatform(arrival, departure, int n)输入 - ... 阅读更多

给定一个硬币列表 C(c1, c2, ……Cn) 和一个值 V。现在的问题是使用最少的硬币数量来构成 V。注意 - 假设有无限数量的硬币 C在这个问题中，我们将考虑一组不同的硬币 C{1, 2, 5, 10}，每种类型的硬币数量无限。为了构成所需的值，我们将尝试取任意类型的最小数量的硬币。例如，对于值 22 - 我们将选择 {10, 10, 2}, ... 阅读更多