Finden alle die sich wiederholende Teilstring in einem gegebenen string

Ich recetly kommen über eine interview-Frage :
Finden alle die sich wiederholende substring in einem angegebenen string mit einer minimalen Größe von 2.
Der Algorithmus sollte effizient sein.

Code für obige Frage wird unten gegeben, 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 implementieren kann, die obige Frage in der Zeit
Komplexität von O(N)?

Wenn Ihre Antwort Suffix-tree oder Hash bitte erläutern Sie es.

Wenn ich das richtig verstehe, betrachten Sie zwei (gleiche Größe) von Teilstrings unterschiedlich in die Ausgabe, wenn Ihre start-Indizes sind unterschiedlich, nicht wenn deren Inhalt unterschiedlich ist, richtig?
Lesen Sie über die suffix-Bäume, meiner Meinung nach, ein wiki ist ein guter start hier: en.wikipedia.org/wiki/Suffix_tree
Sie sind darauf hindeutet, die bestmögliche Lösung zu finden. Wiederholte sub-strings ist ein sehr häufiges problem in CS. Kannst du bitte diesen post als Lösung? Es wird sehr hilfreich für die website-Besucher. Prost!
so wie ich das sehe ist die akzeptierte Antwort enthält die gleichen nach meinem Kommentar, also ich nicht wiederholen möchte, da eine Antwort. Vielleicht sind die einige link sollte Hinzugefügt werden, dass die akzeptierte Antwort.

InformationsquelleAutor IndieProgrammer | 2012-04-07

  1. 5

    Wenn Sie die Ausgabe analysieren Sie die Zeichenfolge "AAAAAAAAAAAAAA", dann gibt es O(n2) Charaktere, also der Algorithmus ist mindestens O(n2).

    Erreichen O(n2), bauen die nur suffix-Baum für jedes suffix von s (Indizes [1..n], [2..n], [3..n], ..., [n..n]). Es spielt keine Rolle, wenn man von den strings hat keine eigene end-Knoten, nur zählen, wie oft jeder Knoten verwendet wird.

    Am Ende, Durchlaufen jeden Knoten mit count>1 und drucken den Weg stellen.

    InformationsquelleAutor ipc

  2. 1

    Das ist nur eine wilde Idee, aber einen Versuch Wert (allerdings ist, benötigt er O(N) Speicher, wobei N die Länge der primären string). Der Algorithmus ist nicht O(N), aber vielleicht kann es optimiert werden.

    Die Idee ist, dass Sie nicht wollen, um string-Vergleiche oft. Können Sie sammeln die hash-Lesen von Daten (zum Beispiel die Summe der ASCII-codes der lese-Zeichen) und vergleichen Sie die hashes. Wenn die hashes gleich sind, werden die Saiten kann gleich sein (es muss überprüft werden, später). Zum Beispiel:

    ABCAB

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

    Weil Sie daran interessiert sind nur in 2+ Länge Werte, die Sie weglassen müssen, den letzten Wert (weil es immer entspricht das einzelne Zeichen).

    Sehen wir zwei gleiche Werte ein: 131 und 198. 131 steht für Sie AB und zeigt das paar, jedoch 198 steht sowohl für ABC und BCA, die abgelehnt werden, durch manuelle Kontrolle.

    Ist es nur die Idee, nicht die Lösung selbst. Die hash-Funktion kann erweitert werden, um Konto die position der Zeichen im Teilstring (oder die Sequenz-Struktur). Storage Methode der hash-Werte können geändert werden, um die Leistung zu verbessern (jedoch in den Kosten von erhöhter Speicherauslastung).

    Hoffe, ich half nur ein bisschen 🙂

    InformationsquelleAutor Spook

  3. 0

    Ich weiß nicht, wie suffix-Baum können alle die sich wiederholende substring, string, "mississippi" bauen suffix-Baum:

    sorry,ich sehe. "Am Ende, Durchlaufen jeden Knoten mit count>1 und Druck seinen Weg." "count" ist, wie viele dieser untergeordnete Knoten 

    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" ---

    InformationsquelleAutor ltqin

Schreibe einen Kommentar