12

Вопрос по algorithm, string, c++ – Чтобы найти все повторяющиеся подстроки в данной строке

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

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

  • @dexametason Вы предлагаете наилучшее из возможных решений. Повторные подстроки - очень распространенная проблема в CS. Можете ли вы опубликовать это как решение? Это будет очень полезно для посетителей сайта. Ура!

    от Apoorv Khurasia
  • Если я правильно понимаю, вы рассматриваете две (одинаковые по размеру) подстроки в выходных данных, если их начальные индексы различны, а не если их содержимое отличается, верно?

    от Skiminok
  • Читайте о деревьях суффиксов, по моему мнению, вики - хорошее начало здесь:en.wikipedia.org/wiki/Suffix_tree

    от dexametason
  • @MonsterTruck, как я вижу, принятый ответ содержит то же самое после моего комментария, поэтому я не хочу повторять его в качестве ответа. Возможно, какую-то ссылку следует добавить к принятому ответу.

    от dexametason
  • 5

    Если вы проанализируете вывод для строки

    "AAAAAAAAAAAAAA"тогда в нем содержится O (n & # xB2;) символов, поэтому алгоритм имеет значение не менее O (n & # xB2;).

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

    В конце переберите каждый узел с количеством & gt; 1 и напечатайте его путь.

  • 1

    Это просто дикая идея

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

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

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

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

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

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

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

  • 0

    Я не знаю

    как дерево суффиксов может получить всю повторяющуюся подстроку, строку "Миссисипи" построить суффиксное дерево вот так:

    извини, понятно & quot; В конце переберите каждый узел с количеством & gt; 1 и напечатайте его путь. & quot; & Quot; подсчет & Quot; сколько это дочерний узел

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