我对 Jon Limjap 的面试事故感到好奇，并开始寻找有效的方法来进行回文检测。我检查了 palindrome Golf 答案，在我看来，答案中只有两种算法，反转字符串并从尾部和头部检查。
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 序列中的精确回文。我环顾四周，没有找到任何关于这种超有效方法的免费文章。
一个好的方法可能是以分而治之的方法并行化第一个版本，为每个线程或处理器分配一对字符数组 1..n 和 length-1-n..length-1。
有什么更好的方法吗？
你知道吗？
只给定一个回文，你必须在 O(N) 内完成，是的。您可以通过按照您所说的方式拆分字符串来提高多处理器的效率。
现在假设您想要进行精确的 DNA 匹配。这些字符串长达数千个字符，而且非常重复。这给了我们优化的机会。
假设您将一个 1000 个字符的长字符串分成 5 对，每对 100,100。代码将如下所示：
isPal(w[0:100],w[-100:]) and isPal(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)...
第二个函数的另一个变体。我们不需要检查正常字符串和反向字符串的右侧部分是否相等。
def palindrome_reverse(s):
l = len(s) // 2
return s[:l] == s[l::-1]
显然，您无法获得比 O(n) 更好的渐近效率，因为每个字符必须至少检查一次。不过，您可以获得更好的乘法常数。
对于单线程，您可以使用汇编来获得加速。您还可以通过一次检查大于一个字节的块中的数据来做得更好，但由于对齐考虑，这可能会很棘手。如果您可以一次检查大至 16 字节的块，那么使用 SIMD 效果会更好。
如果你想并行化它，你可以将字符串分成 N 段，然后让处理器
i[i*n/2, (i+1)*N/2)[L-(i+1)*N/2, L-i*N/2)没有，除非你进行模糊匹配。这就是他们在 DNA 中可能做的事情（我已经用 smith-waterman 在 DNA 中进行了 EST 搜索，但这显然比匹配序列中的回文或反向互补要困难得多）。
它们的复杂度都是 O(N)，所以我认为这些解决方案都不存在任何特定的效率问题。也许我的创意不够，但我不明白如何在少于 N 个步骤的时间内比较 N 个元素，所以像 O(log N) 这样的东西恕我直言绝对是不可能的。
并行性可能会有所帮助，但它仍然不会改变算法的大哦等级，因为它相当于在更快的机器上运行它。
与中心进行比较总是更有效，因为您可以在错过时尽早退出，但它还可以让您进行更快的最大回文搜索，无论您是在寻找最大半径还是所有不重叠的回文。
唯一真正的并行化是如果您有多个独立的字符串要处理。每次未命中都会浪费大量工作，而且未命中的次数总是多于命中的次数。
除了其他人所说的之外，我还为非常大的输入添加了一些预检查标准：
quick check whether tail-character matches
head character
if NOT, just early exit by returning Boolean-False
if (input-length < 4) {
# The quick check just now already confirmed it's palindrome
return Boolean-True
} else if (200 < input-length) {
# adjust this parameter to your preferences
#
# e.g. make it 20 for longer than 8000 etc
# or make it scale to input size,
# either logarithmically, or a fixed ratio like 2.5%
#
reverse last ( N = 4 ) characters/bytes of the input
if that **DOES NOT** match first N chars/bytes {
return boolean-false # early exit
# no point to reverse rest of it
# when head and tail don't even match
} else {
if N was substantial
trim out the head and tail of the input
you've confirmed; avoid duplicated work
remember to also update the variable(s)
you've elected to track the input size
}
[optional 1 : if that substring of N characters you've
just checked happened to all contain the
same character, let's call it C,
then locate the index position, P, for the first
character that isn't C
if P == input-size
then you've already proven
the entire string is a nonstop repeat
of one single character, which, by def,
must be a palindrome
then just return Boolean-True
but the P is more than the half-way point,
you've also proven it cannot possibly be a
palindrome, because second half contains a
component that doesn't exist in first half,
then just return Boolean-False ]
[optional 2 : for extremely long inputs,
like over 200,000 chars,
take the N chars right at the middle of it,
and see if the reversed one matches
if that fails, then do early exit and save time ]
}
if all pre-checks passed,
then simply do it BAU style :
reverse second-half of it,
and see if it's same as first half
使用Python，短代码可以更快，因为它将负载放入更快的VM内部（并且有整个缓存和其他类似的东西）
def ispalin(x):
return all(x[a]==x[-a-1] for a in xrange(len(x)>>1))
您可以使用哈希表来放置字符并拥有一个计数器变量，每当您找到不在表/映射中的元素时，该变量的值就会增加。如果您检查并找到表中已有的元素，则会减少计数。
For odd lettered string the counter should be back to 1 and for even it should hit 0.I hope this approach is right.
See below the snippet.
s->refers to string
eg: String s="abbcaddc";
Hashtable<Character,Integer> textMap= new Hashtable<Character,Integer>();
char charA[]= s.toCharArray();
for(int i=0;i<charA.length;i++)
{
if(!textMap.containsKey(charA[i]))
{
textMap.put(charA[i], ++count);
}
else
{
textMap.put(charA[i],--count);
}
if(length%2 !=0)
{
if(count == 1)
System.out.println("(odd case:PALINDROME)");
else
System.out.println("(odd case:not palindrome)");
}
else if(length%2==0)
{
if(count ==0)
System.out.println("(even case:palindrome)");
else
System.out.println("(even case :not palindrome)");
}
public class Palindrome{
private static boolean isPalindrome(String s){
if(s == null)
return false; //unitialized String ? return false
if(s.isEmpty()) //Empty Strings is a Palindrome
return true;
//we want check characters on opposite sides of the string
//and stop in the middle <divide and conquer>
int left = 0; //left-most char
int right = s.length() - 1; //right-most char
while(left < right){ //this elegantly handles odd characters string
if(s.charAt(left) != s.charAt(right)) //left char must equal
return false; //right else its not a palindrome
left++; //converge left to right
right--;//converge right to left
}
return true; // return true if the while doesn't exit
}
}
虽然我们正在进行 n/2 次计算，但它仍然是 O(n) 这也可以使用线程来完成，但计算会变得混乱，最好避免它。这不会测试特殊字符并且区分大小写。我有可以做到这一点的代码，但是可以修改该代码以轻松处理该问题。