给定一个源字符串s和n相等长度的字符串，我需要找到一种快速算法来返回那些在每个对应位置最多k具有与源字符串不同的字符的字符串。s
这样做的快速算法是什么？
PS：我不得不声称这是一个academic问题。如果可能的话，我想找到最有效的算法。
我也错过了一个非常重要的信息。n相等长度的字符串形成一个字典，将根据该字典查询许多源字符串s。似乎有某种预处理步骤可以提高效率。
问问题
379 次
5 回答
2
我的直觉只是遍历每个 String n，维护一个计数器来计算与 不同的字符数s，但我并不是说它是最有效的解决方案。但是它会是 O(n) 所以除非这是一个已知的性能问题，或者一个学术问题，否则我会同意的。
于 2013-05-03T04:41:54.750 回答
2
Sedgewick 在他的《算法》一书中写道，三元搜索树允许“定位查询词的给定汉明距离内的所有词”。多布博士的文章
于 2013-05-03T06:21:23.850 回答
1
鉴于字符串是固定长度的，您可以计算两个字符串之间的汉明距离以确定相似度；这是字符串长度的 O(n)。因此，最坏的情况是您的算法是 O(nm) 用于将您的字符串与 m 个单词进行比较。
作为替代方案，一个快速的解决方案也是一种内存消耗，就是将你的字典预处理成一个地图。键是一个元组 (p, c)，其中 p 是字符串中的位置，c 是字符串中该位置的字符，值是在该位置具有字符的字符串（因此“the”将在地图中{(0, 't'), "the"}, {(1, 'h'), "the"}, {(2, 'e'), "the"})。要查询映射，遍历查询字符串的字符并使用检索到的字符串构造结果映射；键是字符串，值是从主映射中检索到字符串的次数（因此对于查询字符串“the”，键“thx”的值为 2，键“tee”的值为值为 1)。最后，
当结果映射完成时，您可以通过丢弃不可能等于 K 的键来节省内存。例如，如果 K 为 5，N 为 8，那么当您到达查询字符串的第 4-8 个字符时，您可以丢弃任何尚未在结果映射中的检索字符串，因为它们不可能有 5匹配的字符。或者，当您完成查询字符串的第 6 个字符时，您可以遍历结果映射并删除值小于 3 的所有键。
如果需要，您可以将主要的预计算映射卸载到 NoSql 键值数据库或类似的东西，以节省主内存（而且您不必在每次程序重新启动时都预计算字典）。
您可以将位置和字符连接成一个字符串，而不是将元组 (p, c) 作为键存储在主映射中（因此 (5, 't') 变为“5t”，并且 (12, 'x' ) 变为“12x”)。
于 2013-05-03T05:07:43.870 回答
0
在不知道每个输入字符串中匹配字符的位置的情况下，对于特定字符串，您可能需要检查每个字符，无论您检查它们的顺序是什么。因此，逐个字符地迭代每个字符串并保留不匹配总数的总和。如果i是到目前为止的不匹配数，则在字符串中剩余的未检查字符少于false何时i == k以及何时返回。truek-i
请注意，根据字符串的长度和允许的不匹配数量，迭代整个字符串可能比执行这些检查更快，或者可能仅在每两个字符之后执行它们。试一试，看看如何获得最快的性能。
于 2013-05-03T04:44:36.380 回答
0
如果我们要大声思考，我的方法是：如果不遍历每个n字符串，PI 看不到这样做的方法，但我很高兴得到纠正。在那之后，它将从一个预处理开始，以保存第二组n字符串，以便字符按升序排列。
然后，比较的第一部分将检查每个n字符串，一次检查一个字符，对 sayn'中的每个字符s说s'。
如果s'小于n'则不等于并移动到下一个s'。如果n'小于s'则进入下一步n'。否则记录一个匹配的字符。重复此操作，直到k找到未命中匹配或找到替代匹配并n相应地标记。
为了进一步考虑，可以对每个相邻的字符串进行额外的预处理，n以查看不同字符的总数。这可以在比较字符串时使用n，s如果这些和相邻字符串之间存在足够的差异，n可能不需要比较它？
于 2013-05-04T06:07:50.703 回答