问题标签 [string-algorithm]

问题可以在这里找到： http ://rosalind.info/problems/subs/

我的问题与下面提供的两种解决方案的性能有关。

1.

2.

第二种解决方案漂亮、实用且简短。

第一个解决方案有点大，但它仍然有效。我本可以省略 val 并使用这些值使其更短，但这不是我的目标。

在看到第二个解决方案后，由于代码的长度，我对我的解决方案感到非常失望。检查了 scala 库以了解为什么第二个解决方案有效，然后我自己重新实现了它。考虑检查这两种解决方案的性能，并制作了一条巨大的 3000 万条 DNA 链。

惊讶！

表现：

第一个数字是 DNA 长度，接下来的两个数字表示第一个和第二个解决方案的执行时间（以毫秒为单位）。

11,226,096 - 4921 - 14503

33,678,288 - 6448 - 35150

为什么性能差别这么大？

我试过检查 scala 库，但找不到解释这种行为的东西。

我假设第一个解决方案是创建许多对象，因此会消耗更多内存并花费大量时间，但似乎由于某种原因它工作得更快。我怀疑这是尾递归，我怀疑 zipWithIndex 需要很多时间。迭代器只是迭代器？

谢谢！

给定：
S，一组奇数个n 位字符串
A，一个特定的 n 位字符串

表明任何决定 A 是否在 S 中的算法都必须在最坏的情况下检查 A 的所有 n 位。

通常，我们当然希望必须查看字符串的所有部分才能进行匹配，但是 S 有一些特殊的东西，它有一个奇怪的大小，这让我无法理解。

在一次采访中，我被问到一个关于字符串的问题。问题给出了一个字符串s1= "ABCDBCCDABCD"。和一个模式 "BC"。我们必须用其他字符串（“UVW”或“U”或“uv”）替换此模式。这需要就地到位。

有人提供程序和算法将对您有所帮助。

我正在寻找一种方法来执行文本对齐（左右齐平）。每个输出行的最大宽度为 M 个字符。不允许断词。

例如，请参阅此维基百科页面中的“对齐（左右齐平）”：http://en.wikipedia.org/wiki/Justification_(typesetting)。

我知道有一个动态编程解决方案可以优化左对齐，右对齐，即在行尾均匀分配额外的空间，这样额外空间的成本是最优的（这也被称为“自动换行” '问题或'打印整齐'问题）。但是，对于全文对齐问题，我无法得出动态编程或贪婪方法。

谷歌搜索带我找到基于马尔可夫链编程的文本对齐：http ://www.rose-hulman.edu/Users/faculty/young/OldFiles/CS-Classes/csse220/200820/web/Programs/Markov/justification.html 。但这对我来说似乎很复杂。如果这是对全文证明问题的最佳（也是最简单）的解决方案，那么如果有人能用简单的语言解释同样的问题，那就太好了。

给定一个字符串：“ABCD”，返回具有一个或多个缺失字符的子字符串，保持字符串的顺序。这似乎不是“排列”，但我不确定这个算法是否有名字。我正在使用它来生成单词和单词中单词的字谜。

例子：

A B C D

AB BC CD AC AD << 缺少 BC

ABC BCD ACD ABD

初步说明：string_algo 工作得很好std::wstring，当然，如果我需要来自 string_algo 的算法，我可以（并且确实）首先将 CString 对象转换为 std::wstring。如果我可以直接放入 CString 对象，那就太好了——与现有代码的集成会容易得多！

我想做的事：

正如这里所建议的，我尝试另外包括boost/range/mfc.hpp让Boost.Range 适应 MFC。（虽然我并没有完全理解这个标题，但它似乎对 CString 没有任何作用，只对集合类。）

使用 Visual Studio 2005 提升 1.44.0

测试代码如下所示：

我得到的错误如下所示：

我需要编写一个函数，该函数将返回输入字符串的可能不同循环移位的数量。

您能否给我一些关于我应该从哪里开始以创建高效（就时间复杂度而言）算法的提示？我应该从“预处理”字符串开始并创建一些数据结构来帮助计算以后的班次吗？

我在我的代码中发现了一个问题。当我使用 boost::algorithm::join 时，它可以正常工作，但是当我使用 boost::algorithm::join_if 时，会抛出 bad_cast。我的代码如下：

我的程序的输出是：

我曾经使用过一些 boost::algorithm 函数来处理文本，有几次我使用 过predicates，但从未发生过类似的问题。

我什至尝试将 const char* 替换为 std::string：

但问题还是一样。

编辑： 我想要一个也适用于 C++ 11 之前的 C++ 的解决方案

我有一个从许多不同来源编译的大城市数据库。我正在尝试找到一种根据城市名称轻松发现重复项的方法。天真的答案是使用 levenshtein 距离。但是，城市的问题在于它们通常具有所在国家/地区通用的前缀和后缀。

例如：

布勒维尔与博舍维尔

这些几乎可以肯定是不同的城市。但是，因为它们都以“ville”结尾（并且都以“Bo”开头），所以它们的列文斯坦距离相当小。

*我正在寻找一种字符串距离算法，该算法考虑到字符的位置，通过将单词中间的字母权重于单词末尾的字母来最小化前缀和后缀的影响。*

我自己可能会写一些东西，但我很难相信还没有人发布过合适的算法。

我看到了维基百科页面，但仍然不清楚这个想法。

为了找到 2 个字符串 (T和S) 的最长公共子字符串，我读到我们必须为字符串 构建一个后缀树T($1)S($2)，其中`($1) 和 ($2) 是不属于字符串的特殊字符。

但是字符串的维基百科图像ABAB看起来BABA像这样：

为什么它不包含整个字符串ABAB($1)BABA($2)？不是拼接字符串的后缀吗？

叶子上的数字是什么？