Суперпоследовательность из пакета с нитками

Question

Учитывая строку s, каков наиболее эффективный способ определения самой короткой супер-последовательности s из пакета строк?Кроме того, последний символ s должен соответствовать последнему символу суперструны.

Answer 1

Если я не понял это неправильно, эта проблема, скорее всего, связана с P.

Наивный подход будет следующим:

1. Взять все строки в B, заканчивающиеся тем же символом, что и s.Назовите эту новую сумку B '.Может быть сделано в O (| B |)
2. Выберите все строки, которые являются суперпоследовательностями s в сумке B '.Это можно сделать в O (| B '| * max (| z |)) для z в B. Проверка, является ли данная строка s подпоследовательностью другой строки z, может быть выполнена в O (| z |)
3. Выберите самую короткую из ранее найденных строк (в O (| B '|))

Где | x |означает размер x.

Вы можете объединить эти шаги, но в любом случае это O (| B | * max (| z |)).

Answer 2

Предполагая, что сумка меняется не очень часто, я бы построил DAWG и обыскал ее с помощью *.

Answer 3

Пройдите через каждую строку в сумке, проверяя, является ли s подстрокой, используя быстрый поиск строки, такой как KMP.Проверьте, какая из суперструн самая короткая.Это O(Σlength of strings in bag).

Если вам нужно выполнить поиск несколько раз, вы можете создать три суффикса для каждой строки в сумке и объединить их.Тогда вы можете сделать поиск в O(|s|).