Ich bin kürzlich auf eine Interviewfrage gestoßen: Um alle sich wiederholenden Teilzeichenfolgen in einer bestimmten Zeichenfolge mit einer minimalen Größe von 2 zu finden. Der Algorithmus sollte effizient sein.

Der Code für die obige Frage ist unten angegeben, aber er ist nicht effizient.

<code>#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"));
}
</code>

Meine Frage ist, ob es eine Datenstruktur gibt, die die obige Frage in der zeitlichen Komplexität von O (N) umsetzen kann.

Wenn Ihre Antwort Suffixbaum oder Hashing ist, erläutern Sie dies bitte.