Um alle wiederholenden Teilstrings in einer gegebenen Zeichenfolge zu finden

Question

Ich bin noch auf ein Interview Frage: Um alle wiederholenden Teilstring in einer gegebenen Zeichenfolge mit einer minimalen Größe von 2 zu finden. Der Algorithmus sollte effizient sein.

Code für obige Frage ist unten angegeben, aber es ist nicht effizient.

#include <iostream> 
#include <algorithm> 
#include <iterator> 
#include <set> 
#include <string> 

using namespace std; 

int main() 
{ 
    typedef string::const_iterator iterator; 
    string s("ABCFABHYIFAB"); 
    set<string> found; 

    if (2 < s.size()) 
     for (iterator i = s.begin() + 1, j = s.end(); i != j; ++i) 
      for (iterator x = s.begin(); x != i; ++x) 
      { 
       iterator tmp = mismatch(i, j, x).second;; 
       if (tmp - x > 1) 
        found.insert(string(x, tmp)); 
      } 

      copy(found.begin(), found.end(),ostream_iterator<string>(cout, "\n")); 
} 

Meine Frage ist, dass, gibt es eine Datenstruktur, die obige Frage in der Zeit Komplexität von O (N) umsetzen kann?

Wenn Ihre Antwort Suffix Tree oder Hashing ist, bitte erläutern Sie es.

Answer 1

Wenn Sie die Ausgabe für die Zeichenfolge "AAAAAAAAAAAAAA" analysieren, dann gibt es O (n²) Zeichen in ihm, so ist der Algorithmus mindestens O (n²).

Um O (n²) zu erhalten, erstellen Sie einfach die suffix tree für jedes Suffix von s (Indizes [1..n], [2..n], [3..n], ..., [n. .n]). Es spielt keine Rolle, wenn einer der Strings keinen eigenen Endknoten hat, sondern nur, wie oft jeder Knoten verwendet wird.

Am Ende, iterieren Sie über jeden Knoten mit count> 1 und drucken Sie seinen Pfad.

Answer 2

Das ist nur eine wilde Idee, aber einen Versuch wert (aber es verbraucht O (N) Speicher, wobei N die Länge der primären Zeichenfolge ist). Der Algorithmus ist nicht O (N), aber vielleicht kann er optimiert werden.

Die Idee ist, dass Sie nicht häufig Zeichenfolgenvergleiche machen wollen. Sie können den Hash der gelesenen Daten (zum Beispiel eine Summe von ASCII-Codes gelesener Zeichen) sammeln und die Hashes vergleichen. Wenn die Hashwerte gleich sind, können die Zeichenfolgen gleich sein (dies muss später überprüft werden). Zum Beispiel:

ABCAB 

A -> (65) 
B -> (131, 66) 
C -> (198, 133, 67) 
A -> (263, 198, 132, 65) 
B -> (329, 264, 198, 131, 66) 

Da Sie nur in 2+ Längenwerten interessiert sind, müssen Sie den letzten Wert weglassen (weil es immer auf die einzelnen Zeichen entspricht).

Wir sehen zwei gleiche Werte: 131 und 198. 131 steht für AB und enthüllt das Paar, aber 198 steht sowohl für ABC als auch für BCA, die durch manuelle Prüfung zurückgewiesen werden müssen.

Das ist nur die Idee, nicht die Lösung selbst. Die Hash-Funktion kann erweitert werden, um die Position von Zeichen in Teilstrings (oder der Sequenzstruktur) zu berücksichtigen. Die Speichermethode für Hash-Werte kann geändert werden, um die Leistung zu verbessern (jedoch wegen der erhöhten Speicherauslastung).

Hoffe, dass ich geholfen nur ein wenig :)

Answer 3

Ich weiß nicht, wie Suffixbaum alle die sich wiederholende Teilkette bekommen, string „mississippi“ Suffixbaum wie diese bauen:

sorry, sehe ich. "Am Ende, iteriere über jeden Knoten mit count> 1 und drucke seinen Pfad." "count" ist, wie viele dieser Kindknoten

tree-->|---mississippi    m..mississippi 
     | 
     |---i-->|---ssi-->|---ssippi i .. ississippi 
     |  |   | 
     |  |   |---ppi  issip,issipp,issippi 
     |  | 
     |  |---ppi    ip, ipp, ippi 
     | 
     |---s-->|---si-->|---ssippi s .. ssissippi 
     |  |  | 
     |  |  |---ppi  ssip, ssipp, ssippi 
     |  | 
     |  |---i-->|---ssippi  si .. sissippi 
     |    | 
     |    |---ppi  sip, sipp, sippi 
     | 
     |---p-->|---pi     p, pp, ppi 
       | 
       |---i     p, pi 

--- Suffix Tree for "mississippi" --- 

Answer 4

Ich denke, dieses Problem kann mit dynamischen Programmierung auch gelöst werden.