Учитывая n строк, является ли одна из них подстрокой другой?

Предположим, нам дан набор из строк, S 1 , … , S n . Я хотел бы знать, является ли какая-либо из этих строк подстрокой любой другой строки в коллекции. Другими словами, я хотел бы алгоритм для следующей задачи:$n$$S_1,\dots,S_n$

Ввод: $S_1,\dots,S_n$

Вывод: такой, что S i является подстрокой S j и i ≠ j , или None, если таких i , j не существует$i,j$$S_i$$S_j$$i\ne j$$i,j$

Есть ли эффективный алгоритм для этого?

Если мы заменим «подстроку» на «префикс», то получится эффективный алгоритм (отсортируйте строки, затем выполните линейное сканирование для сравнения соседних строк; сортировка обеспечит смежность подстрок). Но кажется более сложным проверить, является ли какая-либо строка подстрокой какой-либо другой строки. Наивным алгоритмом является итерация по всем парам , но для этого требуется subst ( n 2 ) тестов подстрок. Есть ли более эффективный алгоритм?$i,j$$\Theta(n^2)$

Я думаю, мы могли бы назвать это "тестирование подстрок всех пар" или что-то в этом роде.

Моя конечная цель - обрезать коллекцию, чтобы ни одна строка не являлась подстрокой какой-либо другой, удаляя каждую из подстрок чего-то еще в коллекции.

Вы можете построить дерево суффиксов за линейное время и проверить, есть ли внутренний узел, соответствующий полной строке (постоянное время на узел).

$s_1, \dots, s_n \in \Sigma^*$

1. $s_1\$_1, s_2\$_2, \dots, s_n\$_n$$n$$\$_1,\dots,\$_n \notin \Sigma$

   Используя алгоритм Укконена , это можно сделать за линейное время; линейный в сумме всех длин строк.

2. $(i,j)$$s_i[j..|s_i|]$$s_i$$n$$(i,0)$

   Это занимает время, линейное по размеру дерева, которое само по себе является линейным по входному размеру.

3. $(i,0)$$\$_i$$(i,0)$

   Это снова занимает линейное время.

Отдельные терминальные маркеры на самом деле не нужны; одного, используемого для завершения всех строк, вполне достаточно, если вы разрешаете использовать несколько меток на листе.