我对乔恩·林贾普（Jon Limjap）的采访事故感到好奇，并开始寻找有效的方法来进行回文检测。我检查了回文高尔夫球场的答案，在我看来，答案中只有两个算法，即反转字符串并从尾巴和头部进行检查。
def palindrome_short(s): length = len(s) for i in xrange(0,length/2): if s[i] != s[(length-1)-i]: return False return True def palindrome_reverse(s): return s == s[::-1]
我认为这些方法都不能用于检测巨大DNA序列中的精确回文。我四处张望，却没有找到任何免费的文章介绍这可能是一种超高效的方法。
一个好的方法可能是采用分而治之的方法并行化第一个版本，为每个线程或处理器分配一对char数组1..n和length-1-n..length-1。
有什么更好的方法？
你知道任何？
仅考虑一个回文，您将必须在O（N）中进行，是的。如您所说，通过分割字符串可以使多处理器获得更高的效率。
现在说您要进行精确的DNA匹配。这些字符串的长度为数千个字符，并且非常重复。这使我们有机会进行优化。
假设您将1000个字符的字符串分成5对100,100。该代码将如下所示：
isPal(w[0:100],w[-100:]) and isPail(w[101:200], w[-200:-100]) ...
等等…第一次进行这些匹配时，您将不得不对其进行处理。但是，您可以将完成的所有结果添加到哈希表对对的布尔值映射中：
isPal = {("ATTAGC", "CGATTA"): True, ("ATTGCA", "CAGTAA"): False}
等等…这将占用太多内存。对于100,100对，哈希映射将具有2 * 4 ^ 100个元素。假设您仅存储两个32位的字符串哈希作为键，那么您将需要10 ^ 55兆字节，这太可笑了。
也许如果您使用较小的字符串，该问题可能很容易解决。然后，您将拥有一个巨大的哈希图，但是至少回文（假设10x10对将采用O（1）），因此检查1000字符串是否是回文将需要100次查找而不是500次比较。仍然是O（N）…
