Чтобы найти всю повторяющуюся подстроку в заданной строке

Я натолкнулся на вопрос интервью: Найти всю повторяющуюся подстроку в заданной строке с минимальным размером 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)?

Если ваш ответ - дерево суффикса или Хешинг, пожалуйста, уточните его.

Ответ 1

Если вы анализируете вывод для строки "AAAAAAAAAAAAAA", то в ней есть символы O (n²), поэтому алгоритм не менее O (n²).

Чтобы достичь O (n²), просто создайте дерево сущностей для каждого суффикса s (индексы [1..n], [2..n], [3..n],..., [n..n]). Не имеет значения, если одна из строк не имеет собственного конца node, просто подсчитайте, как часто используется каждый node.

В конце проведите по каждому node со значением count > 1 и напечатайте его путь.

Ответ 2

Это просто дикая идея, но стоит попробовать (однако она потребляет память O (N), где N - длина первичной строки). Алгоритм не O (N), но, возможно, он может быть оптимизирован.

Идея состоит в том, что вы не хотите часто проводить сравнения строк. Вы можете собрать хэш данных чтения (например, сумму кодов ASCII считываемых символов) и сравнить хэши. Если хеши равны, строки могут быть равными (это нужно проверить позже). Например:

ABCAB

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

Поскольку вам интересны только значения длины + +, вы должны опустить последнее значение (потому что оно всегда соответствует одиночному символу).

Мы видим два равных значения: 131 и 198. 131 означает AB и показывает пару, однако 198 стоит как для ABC, так и для BCA, которые должны быть отклонены вручную.

Это только идея, а не само решение. Хеш-функция может быть расширена для учета позиции символа в подстроке (или структуре последовательности). Метод хранения хеш-значений может быть изменен для повышения производительности (однако, это связано с увеличением использования памяти).

Надеюсь, я немного помог:)

Ответ 3

Я не знаю, как дерево суффиксов может получить всю повторяющуюся подстроку, строковое суффикс дерева "mississippi" выглядит следующим образом:

Извините, я вижу. "В конце проведите по каждой из node со счетом > 1 и напечатайте ее путь". "count" - это количество этого дочернего node

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

Ответ 4

Я думаю, что эту проблему можно решить и с помощью динамического программирования.