Какой алгоритм можно использовать для поиска повторяющихся фраз в строке?

Суффиксные деревья - хороший способ реализовать это. Внизу статьи есть ссылки на реализации на разных языках.

Как сказал jmah, для этого вы можете использовать суффиксные деревья / суффиксные массивы.

Есть описание алгоритма, который вы могли бы использовать здесь (см. Раздел 3.1).

Вы можете найти более подробное описание в цитируемой ими книге (Gusfield, 1997), которая называется в гугл книгах.

Как и ранее, люди упоминали, что суффиксное дерево - лучший инструмент для работы. Мой любимый сайт для деревьев суффиксов - http://www.allisons.org/ll/AlgDS/Tree/Suffix/. Он перечисляет все изящные варианты использования суффиксных деревьев на одной странице и имеет встроенное тестовое приложение js для тестирования строк и работы с примерами.

В теории

• массив суффиксов - «лучший» ответ, поскольку он может быть реализован для использования линейного пространства и времени для обнаружения любых повторяющихся подстрок. Однако наивная реализация на самом деле требует времени O (n ^ 2 log n) для сортировки суффиксов, и не совсем очевидно, как уменьшить это до O (n log n), не говоря уже о O (n), хотя вы можете прочитать сопутствующие документы, если хотите.
• суффиксное дерево может занимать немного больше памяти (хотя и линейно), чем массив суффиксов, но его проще реализовать для быстрого построения, поскольку вы можете использовать что-то вроде идеи сортировки по основанию при добавлении элементов в дерево (см. Ссылку на wikipedia из имя для подробностей).
• Также следует помнить о Алгоритм KMP, который специализируется на очень быстром поиске конкретной подстроки в более длинной строке. Если вам нужен только этот особый случай, просто используйте KMP и не нужно сначала создавать индекс достаточности.

На практике

Я предполагаю, что вы анализируете документ, состоящий из слов на естественном языке (например, английского), и на самом деле хотите что-то сделать с собранными вами данными.

В этом случае вы можете просто провести быстрый анализ н-грамм для небольшого числа n, такого как n = 2 или 3. Например, вы можете разметить свой документ в виде списка слов, удалив знаки препинания, заглавные буквы и перевод строки. слова (работает, запускает оба -> «запустить») для увеличения семантических совпадений. Затем просто создайте хеш-карту (например, hash_map в C++, словарь в python и т.д.) каждой смежной пары слов с учетом ее количества появлений на данный момент. В итоге вы получаете очень полезные данные, которые очень быстро кодировались, а запускались не очень медленно.

предположим, вам дан отсортированный массив A с n записями (i = 1,2,3, ..., n)

Algo(A(i))
{
  while i<>n
  {
    temp=A[i];
    if A[i]<>A[i+1] then
    {     
      temp=A[i+1];
      i=i+1;
      Algo(A[i])
    }
    else if A[i]==A[i+1] then
      mark A[i] and A[i+1] as duplicates
  }
}

Этот алгоритм выполняется за время O (n).