Ich wurde neugierigJon Limjaps Interview-Missgeschick und suchte nach effizienten Methoden zur Palindromerkennung. Ich habe das überprüftPalindrome Golf Antworten und es scheint mir, dass in den Antworten nur zwei Algorithmen sind, die den String umkehren und von Schwanz und Kopf prüfen.

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]

Ich denke, keine dieser Methoden wird zum Nachweis exakter Palindrome in riesigen DNA-Sequenzen verwendet. Ich habe mich ein wenig umgesehen und keinen kostenlosen Artikel darüber gefunden, wie effizient dies sein könnte.

Ein guter Weg könnte darin bestehen, die erste Version in einem Divide-and-Conquer-Ansatz zu parallelisieren und jedem Thread oder Prozessor ein Paar von char-Arrays 1..n und length-1-n..length-1 zuzuweisen.

Was wäre ein besserer Weg?

Kennst du welche?