回文检测效率

仅考虑一个回文，您将必须在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）…