问题标签 [string-algorithm]

我们有一个字符串s，包含小写字母 (az)。我们可以用任何其他字符替换任何字符，并且可以多次这样做。

我们可以从 中创建一个回文字符串p，s使得 中p包含给定的特定单词（即假设linkedin）。现在，我们需要找到将字符串转换s为p.

ex - s=linkedininininin 那么回文字符串p是linkedinnideknil，结果是 6。

第二个例子（为了更清楚） - s=linkaeiouideknil 然后p=和结果linkedinnideknil将是 4，因为我们将替换a为e、和。edoun

我试图通过获取 s 和 p 的 LCS 并从 s 的长度中减去它来解决它。但问题是我如何确保回文保证包含给定的单词（Linkedin）？

请提供您的方法。谢谢。

请问，如何解决以下问题：

如何找到给定字符串中出现频率最高的子字符串？例如字符串：

acd0a55b171241cc13afc7135acd09d609f9e4928e18908e6f6fb5574b4ac13731f993031a13f

在这个字符串中有子字符串acd0和c13. 还有子字符串13等等。

如何查找所有出现的按字符数排列的子字符串？

例如：

acd0: 4 个字符 2 次

c13: 3 个字符 2 次

13: 2 个字符 2 次！

实际13出现 4 次但已经出现 2 次c13，因此不允许再次计算。

解决方案应该在 Bash 中。

我有一个字符串（你好，这是一个字符串），我想在其中搜索一个关键字。我该怎么做？

我必须在字符串中搜索以下关键字：

字符串：您好，这是一个字符串。

关键词： 1. Hello this（应匹配） 2. Hello（应匹配） 3. Hello t（应不匹配） 4. Hello this i（应不匹配）

请建议构造数据结构来存储和搜索的优化方法？

我想在 n 个查询的字符串中找到一个字符的出现：例如，字符串是：“i_love_mathematics”，任务是找到：

“我”在范围内：

'_' 在范围内：

输出将是：

类似的问题是查找字符串中字符的出现次数，但复杂度为 O(N) 但在这种情况下，如果我这样做会导致非常高的复杂度，是否有一种数据结构可以可以用来解决这个问题吗？

我在 Haskell 做一个任务。任务是在给定单词匹配、未命中和间隙插入分数的情况下给出两个字符串的最佳对齐方式。到目前为止，这是我们的代码。第一步是使用蛮力使其工作，稍后我们将使用记忆化来实现。但是，我们被困在当前位置。

我们的 optAlignment 函数无法正常工作。对于示例输入“writers”“vintner”，返回的最佳对齐应该是：

但我们得到

所以正确的替代方案是存在的，但也有更多。我们制作了一个函数 totalScore，它表明我们得到的一些备选方案不是最优的（显然）。但是我们现在已经花了 2 个小时试图弄清楚，但没有取得任何进展。该代码还需要几分钟才能运行，这使得错误检查有点困难。

所以我们真的需要一些帮助来找出我们代码中的哪些部分是错误的。

我想解决以下算法问题。给定一组字符串 s1, s2, ..., sn。我想找到一个字符串 s_e，它包含所有 n-gram，它们存在于所有输入字符串中。

考虑一个包含以下三个字符串的示例：

n-gram 是（我用星号标记了至少一个字符串中缺少的 n-gram）：

所以解决方案应该包含 n-gram：“A”、“B”、“C”、“AB”、“BA”、“BC”、“ABC”。因此最短的字符串是“BABC”。它包含一个 n-gram，它并不存在于所有输入字符串中，即“BABC”，但这没关系。

结果字符串我称为 n-gram 提取器，因为通过遍历结果的所有 n-gram，您可以获得所有 n-gram，它们存在于所有输入字符串中。

如果这是一个已知问题，我很乐意知道它的名称。（是：我以为我有一个解决方案的想法，但结果我没有）。

对于输入，可以安全地假设字母大小的平方 (n^2) 小于最短字符串的长度。

我需要一种方法来帮助我在另一个子字符串中找到一个字符串，或者换句话说，在另一个字符串的子范围内找到一个字符串。此外，我需要以相反的顺序找到它，因为我知道我要查找的字符串接近用作“干草堆”的子字符串的末尾。

让我们假设以下一段代码，rfind_in_substr我要求的方法在哪里：

当然，第 (1) 行可以替换为：

但这意味着子字符串的不必要副本。是否有任何方法或 C++/boost 方法可以帮助我做到这一点？

我在看boost::algorithm::string图书馆，但我什么也没找到（我已经理解了）。我知道 C++17 有这个std::string_view类，那将是完美的，但我使用的是 C++14。

我在网上发现了这个非常具有挑战性的编码问题，我想尝试一下。

总体思路是给定文本字符串T和模式P，找到该模式的出现，总结它的对应值并返回最大值和最小值。如果您想更详细地阅读该问题，请参阅此。

但是，下面是我提供的代码，它适用于一个简单的测试用例，但是在多个复杂的测试用例上运行时它非常慢，而且我不确定我的代码需要在哪里优化。

任何人都可以在我弄错逻辑的地方帮忙。

KMP算法

代码归功于Github

我正在处理一个问题，它要求您在按字典顺序排序的排列中找到字符串的排名。

O(N^2) 很清楚。

一些网站也有O(n) 解决方案。优化的部分基本上是预先填充一个count array这样的

count[i] 包含 str 中存在且小于 i 的字符数。

我知道这会降低复杂性，但我无法理解我们如何计算这个数组。这是执行此操作的函数（取自链接）：

有人可以提供这个功能的直观解释吗？

给定一个二进制字符串。如何在字符串的某个范围内查找“010”的出现。
例如，我有字符串"0100110"。如果给定的范围是3 7（基于 1 的索引），那么输出将为4。我找不到任何更快的方法来解决它。

在尝试这个时，我可以在O(N)复杂度中解决它。方法是 - 首先我指出所有“1”在一定范围内的位置，并使用这些位置我将计算来回“0”的数量。然后将后面找到的“0”数乘以单个“1”与第四次找到的“0”数。然后将一定范围内的每个'1'的乘积相加。

对于给定的示例，“1”在范围内的位置是{5, 6}。现在对于索引5，我前后的“0”数分别为2和1。所以我们可以让子序列"010"是2。同样对于索引6我们也得到答案是2。总共我们可以使子序列“010”总共是4次。

但是当我们对给定字符串有一定范围的Q查询时，我的方法很容易达到时间复杂度O(N ² )。我尝试了很多，但未能找到优化它的方法。任何人都可以用一种小于O(N ² )复杂度的方法来帮助我吗？顺便提一下时间限制应该是1秒。如果您提供伪代码，那将是一个加号。

〜提前谢谢。