Я часто сталкиваюсь с вопросом интервью: Чтобы найти все повторяющиеся подстроки в заданной строке с минимальным размером 2. Алгоритм должен быть эффективным.
Код для вышеуказанного вопроса приведен ниже, но он не эффективен.
#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"));
}
Мой вопрос заключается в том, существует ли какая-либо структура данных, которая может реализовать вышеупомянутый вопрос во времени. сложность O(N)?
Если ваш ответ — дерево суффиксов или хеширование, пожалуйста, уточните его.