Zählen Palindrom Teil in O (n)

einen String Given (nur englische Zeichen annehmen) S der Länge n, wir die Anzahl der Palindrom-Teil mit dem folgenden Algorithmus zählen:Zählen Palindrom Teil in O (n)

for i = 0 to |S| do 
    p1 = number of palindromes centered in i (odd length) 
    p2 = number of palindromes centered in i and i+1 (even length) 

    add p1 + p2 to total number of palindromic substrings of S

Der obige Code O(n^2) ist jedoch. Ich bin an einem Algorithmus interessiert, der dieses Problem in O(n) löst. Ich weiß sicher, dass es einen gibt, da ich gehört habe, dass mehrere Leute sagen, dass es das tut, und das Problem existiert auf einer lokalen Online-Richter-Seite mit einer Obergrenze von 1 000 000 auf n, aber ich habe den Algorithmus noch nie gesehen und kann nicht scheinen dazu in der Lage zu sein.

Update:

Die allgemeine Idee, die ich habe, ist len[i] = length of the longest palindrome centered at the character 2i + 1 und eine ähnliche Anordnung für even-Länge Palindrome zu berechnen. Mit einer guten Buchhaltung sollte es möglich sein, dies in O(1) für jedes Zeichen zu berechnen, was es uns ermöglichen wird, viele Palindrome auf einmal zu zählen. Ich bin fest, wie genau ich das berechnen soll.

Ich werde eine Lösung akzeptieren, die O(n) und vielleicht sogar O(n log n) zusätzlichen Speicher verwendet. Ich denke, das ist ohne sie unmöglich.

Alle guten Ideen oder Referenzen sind willkommen.

Quelle

2010-09-05 IVlad

Was lässt Sie denken, dass die Lösung O (n) Zeit ist? Außerdem ist es ziemlich seltsam, einen O (n) -Zeitalgorithmus zu haben, der O (n log n) -Raum benötigt. –

@Strilanc - Ich denke, es ist O (n), weil das die Komplexität ist, die von einigen Leuten erwähnt wird und die einzige Sache, die in 0,1 Sekunden auf einer Million Zeichen laufen könnte. – IVlad

Related: [Schreiben Sie eine Funktion, die das längste Palindrom in einer gegebenen Zeichenfolge zurückgibt] (http://stackoverflow.com/q/1115001/54262) –

Die folgende Seite zeigt einen Algorithmus zur Berechnung der längsten palindromischen Teilkette in O (n) -Zeit, indem die längste palindromische Teilkette in jedem möglichen Zentrum berechnet und dann das Maximum genommen wird. Also sollten Sie es leicht für Ihre Zwecke modifizieren können.

http://www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-in-linear-time/

EDIT: Der erste Link sieht ein wenig wackelig bei genauerem Hinsehen, also hier ist ein anderes:

http://zhuhcheng.spaces.live.com/Blog/cns!DE38E96268C49F28!311.entry?wa=wsignin1.0&sa=707413829

Quelle

2010-09-06 05:44:36

Ich verstehe nicht wirklich, wie sie P [i] in Ihrem zweiten Link berechnen. Kannst du darüber klarstellen? Alles, was ich sehe, sind ein paar Ungleichheiten, aber nichts darüber, wie man P tatsächlich berechnet. Ihr erster Link ist in dieser Hinsicht viel klarer, aber einige Leute sagen, dass er tatsächlich quadratisch ist. Ich werde meine eigene Implementierung schreiben und für mich selbst testen. – IVlad

Ich übersetzte den Python-Code in Ihrem ersten Link zu C++ und es sieht so aus, als wäre es O (n). Es läuft sofort für eine Zeichenfolge, die aus einem einzelnen Zeichen besteht, und es besteht auch jeden Test, den ich ausprobiert habe. Sieht so aus, als wäre es das, danke! – IVlad

Es geht um das Maximum Palindrom, und es überspringt auch das kleine Palindrom, wenn es einen größeren gefunden hat. Ich frage mich, ob Sie in der Lage waren, das ganze Palindrom zu zählen, indem Sie diesen Algorithmus modifizieren? –

Für „normale“ Strings sollte es ziemlich effizient sein bei jedem Charakter als das Potential „center“ suchen eine Palindrom und dann prüfen, ob die umliegenden Zeichen man eigentlich bauen:

# check odd palindromes 
for center in range(len(ls)): 
    # check how many characters to the left and right of |center| 
    # build a palindrome 
    maxoffs = min(center, len(ls)-center-1) 
    offs = 0 
    while offs <= maxoffs and ls[center-offs] == ls[center+offs]: 
     offs += 1 
    offs -= 1 
    print ls[center-offs : center+offs+1]          

# check for even palindromes 
for center in range(len(ls)-1): 
    maxoffs = min(center, len(ls)-center-2) 
    offs = 0 
    while offs <= maxoffs and ls[center-offs] == ls[center+offs+1]: 
     offs += 1 
    offs -= 1 
    if offs >= 0: 
     print ls[center-offs : center+offs+2]

Für normale Strings dieser sollte etwa O (n) sein, obwohl im schlimmsten Fall, zum Beispiel wenn die Zeichenfolge nur aus einem Zeichen besteht, immer wieder wiederholt wird, wird es immer noch O (n) Zeit dauern.

Quelle

2010-09-05 19:59:16 sth

Sie können die Suche in der Tat früh stoppen, die für zufällige Zeichenfolgen gut genug sein wird. Ich interessiere mich für etwas, das immer 'O (n)' ist. Es ist sehr leicht, dies zu brechen: eine Zeichenfolge, die aus einem einzelnen Zeichen besteht. – IVlad

S="aaabb" einen String in Betracht.

ein Zeichen Append '$' an beiden Enden der Schnur und in zwischen jeweils zwei aufeinanderfolgende Zeichen der Zeichenfolge zu S="$a$a$a$b$b$" und Manacher's algorithmS für diese Saite ändern gelten.

Die neue Zeichenfolge S hat die Länge 2n + 1, was uns die Laufzeit von O (2n + 1) gibt, was dasselbe wie O (n) ist.

index : 1 2 3 4 5 6 7 8 9 10 11 
A  : 1 3 5 7 5 3 1 3 5 3 1 
S  : $ a $ a $ a $ b $ b $

Array A ist das Ergebnis von Manachers Algorithmus.

nun die Summe von A[i]/4 für Index, in dem '$', sonst (A[i]+1)/4 für jedes andere Zeichen von 1 < = i < = n ist die Antwort.

Hier fungiert $ als ein Zentrum für die gerade Länge palidromic Teilstrings und die ungerade Länge kann normal berechnet werden. Die Antwort für diesen Fall ist:

0 + 1 + 1 + 2 + 1 + 1 + 0 + 1 + 1 + 1 + 0 = 9 (a, a, aaa, a, b, b, aa , aa, bb).

Quelle

2017-01-14 14:37:31

Zählen Palindrom Teil in O (n)

Antwort

Verwandte Themen