N-граммовый экстрактор
Я хочу решить следующую алгоритмическую задачу. Дан набор строк s1, s2, ..., sn. Я хочу найти строку s_e, которая содержит все n-граммы, которые существуют во всей входной строке.
Рассмотрим пример с тремя следующими строками:
ABABC
BABCA
ABCBA
N-граммы (я отмечаю n-граммами, которые отсутствуют хотя бы в одной строке, звездочкой):
A B C
AB BA BC CA* CB*
ABA* BAB* ABC BCA* BCB* CBA*
ABAB* BABC* ABCA* ABCB* BCBA*
ABABC* BABCA* ABCBA*
Поэтому решение должно содержать н-граммы: "А", "В", "С", "АВ", "ВА", "ВС", "АВС". Таким образом, самая короткая такая строка - "BABC". Он содержит n-грамм, которого нет во всех входных строках, а именно "BABC", но это нормально.
И полученную строку я назвал экстрактором n-граммы, потому что, перебирая все n-граммы результата, вы можете получить все n-граммы, которые присутствуют во всех входных строках.
Если это известная проблема, я был бы рад узнать ее название. (было: я думал, что у меня есть идея для решения, но оказалось, что нет).
Для ввода можно с уверенностью предположить, что квадрат размера алфавита (n^2) меньше, чем длина самой короткой строки.