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

Question

Рассмотрим следующую алгоритмическую проблему: учитывая список строк $ l= [s_1, s_2, \ dots, s_n] $ , мы хотим знать все пары < Spaness Class="Math-container"> $ (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 subsequence of y:
4.         OUTPUT x,y

.

Тем не менее, это имеет сложность $ O (n ^ 2 \ Cdot m) $ - Мне интересно, есть ли более быстрый алгоритм (быстрее учитывая, что Количество пар $ (x, y) $ намного меньше, чем $ n $ , поэтому, например, Алгоритм со сложностью в зависимости от количества продуктивных пар).

Обратите внимание, что этот вопрос выполняется до Этот вопрос , который примерно такой же проблемы, но для подстроки (не подпоследовательности). Там алгоритм Aho-Corasick решил свою проблему идеально - есть, может быть, что-то так, но для подпоследовательности?

Answer 1

Нет, невозможно лучше делать, если не проходит сильная гипотеза экспоненциального времени (SETH). Если бы мы могли решить эту проблему существенно быстрее, чем $ O (n ^ 2) $ Мы немедленно получили бы гораздо более быстрый алгоритм для решения проблемной проблемы с полной NP. Это верно даже для $ m $ немного больше, чем $ \ log (n) $ и дело в Что мы хотим решить, существует ли такая пара $ (x, y) $ вообще.

См., Например, Эти лекционные ноты в разделе 3 " Нижние границы для ортогональных векторов ». Доказательство аналогично доказательству теоремы 2 в этих лекциях.

Во-первых, мы рассмотрим более общую проблему данных двух наборов строк $ x, y $ , находя какую-нибудь строку в $ y $ .

Учитывая формулу SAT, мы разделяем его $ n $ Переменные на два равных набора $ n / 2 $ < / span> Переменные. В $ \ SIGMA $ Мы принимаем персонаж, соответствующий каждому пункту. В $ x $ мы добавляем строку для каждого возможного назначения первой половине переменных, с символом, соответствующим каждому пункту не удовлетворены этими переменными. Между тем, в $ y $ , мы добавляем строку для каждого назначения во вторую половину переменных, с символом для каждого пункта, который удовлетворен этими переменными. Очевидно, что формула выполнена, если и только если какая-то строка в $ x $ является подпоследовательностью некоторой строки в $ y $ $ .

Если эта проблема может быть решена существенно быстрее, чем $ O (n ^ 2) $ , то это дает существенно более быстрый алгоритм для удовлетворения, чем $ 2 ^ n $ . Предположим, проблема может быть решена в $ O (n ^ {1.99}) $ time, то удовлетворенность может быть решена в $ (2 ^ {N / 2}) ^ {1.99}= O (2 ^ {0,996n}) $ Что противоречит seth.

В вашей проблеме есть только один набор строк, все из которых может быть подпоследовательностью друг друга. Это, однако, не проблема, так как мы можем просто изменить строки в нашем случае так, что ни одна строка $ y $ - это подпоследовательность любой другой строки (например, путем заполнения Все строки в $ y $ , чтобы иметь ту же длину), и аналогичным образом прокладывают каждую строку в $ x $ К той же длине, что и другие строки в $ x $ (но существенно короче строк в $ y $ ) ,

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