Учитывая список строк, найдите каждую пару $ (x, y) $, где $ x $ - это подстрока $ y $.Возможно сделать лучше, чем $ O (N ^ 2) $?

Question

Рассмотрим следующую алгоритмическую проблему: учитывая список строк $ l= [s_1, s_2, \ dots, s_n] $ , мы хотим знать все пары < SPAN CLASS= «Математический контейнер»> $ (x, y) $ где $ x $ - это подстрока $ y $ . Мы можем предположить, что все строки имеют длину при максимальном уровне $ m $ , где $ m << n $ и Все на конечный алфавит $ \ sigma $ с $ | \ sigma | << n $ . Мы также можем предположить, что количество пар $ (x, y) $ где $ x $ Подменная строка $ y $ намного меньше, чем $ n $ .

Тривиальный алгоритм будет так:

1. foreach x in L:
2.   foreach y in L:
3.      if x is substring of y:
4.         OUTPUT x,y

.

Тем не менее, это имеет сложность $ O (n ^ 2 \ cdot m) $ - Мне интересно, есть ли более быстрый алгоритм?

Edit : Как указано в комментариях, там может быть максимально $ n ^ 2 $ такие пары, поэтому я не вижу, как может быть алгоритм быстрее, чем $ O (n ^ 2) $ . Тем не менее, мне было интересно, есть ли что-то вроде алгоритм $ p-fpt $ , где квадратная сложность зависит от количества выходных пар, а не $ n $ ? Или, по крайней мере, алгоритм, который уменьшает сложность к чему-то лучшему, чем $ O (N ^ 2 \ Cdot M) $ .

Answer 1

Это можно решить с Aho-Corasick Algorithm в < Spaness Class="Математический контейнер"> $ o (nm + mm) $ time, где $ m $ - это количество пар, выводимых.

Сначала создайте автомат AHO-CORASICK для набора строк в $ O (NM) $ время. Затем запустите каждую строку через автомат - это требуется $ O (NM) $ Время работы строк через автомат и $ O (mm) $ Время для вывода совпадений, потому что одна и та же строка может совпадать $ m $ Times в худшем случае. (Например, ab соответствует ababab 3 раза.)

---

Это может быть улучшено до истинного линейного $ o (l + m) $ time, где $ l $ Общая длина строк и $ m $ - это количество совпадений:

При запуске строк через автомат хранится для каждого узла Automaton Индекс предыдущей строки, для которого был посещен этот узел. При выводе совпадений останавливайте следующие ссылки словаря, если ссылка приводит к узлу, которое уже было посещено для этой строки - вы уже вывели все совпадения, которые находятся в возрасте от этого узла. Теперь каждый матч выводится ровно один раз, и мы пересекаем словарные ссылки только тогда, когда вывод новых совпадений.