Как найти набор кратчайших подпоследовательностей с минимальными столкновениями из множества строк

У меня есть список строк, например

Foobar
Foobaron
Foot
табурет
barfoo
вольная

Я хочу найти набор кратчайших возможных подпоследовательностей, которые уникальны для каждой строки в наборе; символы в каждой подпоследовательности не должны быть смежными, только по порядку, как они появляются в исходной строке. В приведенном выше примере это будет (по другим возможностям)

Fb (как уникальный для Foobar по мере его возникновения, столкновение с Foobaron неизбежным)
Fn (уникально для Foobaron, другого ...F...n...)
Ft (Нога)
bs (barstool)
bf (barfoo)
e (footloose)

Существует ли эффективный способ разбить такие последовательности и свести к минимуму количество сталкивающихся строк (когда нельзя избежать столкновений, например, когда строки являются подстроками других строк) из заданного массива строк? Точнее, выбирая длину N, каков будет набор подпоследовательностей до N символов, каждый из которых идентифицирует исходные строки с наименьшим числом столкновений.

Ответ 1

Я бы на самом деле не назвал это "эффективным", но вы можете сделать это лучше, чем просто немой:

words = ['Foobar', 'Foobaron', 'Foot', 'barstool', 'barfoo', 'footloose']
N = 2
n = len(words)
L = max([len(word) for word in words])

def generate_substrings(word, max_length=None):
    if max_length is None:
        max_length = len(word)
    set_substrings = set()
    set_substrings.add('')
    for charac in word:
        new_substr_list = []
        for substr in set_substrings:
            new_substr = substr + charac
            if len(new_substr) <= max_length:
                new_substr_list.append(new_substr)
        set_substrings.update(new_substr_list)
    return set_substrings

def get_best_substring_for_each(string_list=words, max_length=N):
    all_substrings = {}
    best = {}
    for word in string_list:
        for substring in generate_substrings(word, max_length=max_length):
            if substring not in all_substrings:
                all_substrings[substring] = 0
            all_substrings[substring] = all_substrings[substring] + 1
    for word in string_list:
        best_score = len(string_list) + 1
        best[word] = ''
        for substring in generate_substrings(word=word, max_length=max_length):
            if all_substrings[substring] < best_score:
                best[word] = substring
                best_score = all_substrings[substring]
    return best

print(get_best_substring_for_each(words, N))

Эта программа печатает решение:

{'barfoo': 'af', 'Foobar': 'Fr', 'Foobaron': 'n', 'footloose': 'os', 'barstool': 'al', 'Foot': 'Ft'}

Это может быть легко улучшено с помощью постоянного фактора, например, путем хранения результатов generate_substrings вместо вычисления его дважды.

Сложность O(n*C(N, L+N)), где n - количество слов, L - максимальная длина слова, а C(n, k) - количество комбинаций с k элементами из n.

Я не думаю (не уверен, хотя), что вы можете сделать гораздо лучше в худшем случае, потому что, кажется, трудно не перечислить все возможные подстроки в худшем случае (последний, который будет оцениваться, может быть единственным без избыточности...). Возможно, в среднем вы можете сделать лучше...

Ответ 2

Вы можете использовать модификацию для самого длинного общего алгоритма подпоследовательности. В этом случае вы ищете кратчайшую уникальную подпоследовательность. Ниже приводится часть решения динамического программирования, которое более эффективно, чем рекурсивное решение. Изменения в самом длинном общем алгоритме подпоследовательности описаны в комментариях ниже:

for (int i = 0; i < string1.Length; i++)
    for (int j = 0; j < string2.Length; j++)
        if (string1[i-1] != string2[j-1])   // find characters in the strings that are distinct
            SUS[i][j] = SUS[i-1][j-1] + 1;  // SUS: Shortest Unique Substring
        else
            SUS[i][j] = min(SUS[i-1][j], SUS[i][j-1]);  // find minimum size of distinct strings

Затем вы можете поместить этот код в функцию и вызвать эту функцию для каждой строки в вашем наборе, чтобы найти длину самой короткой уникальной подпоследовательности в наборе.

Как только у вас будет длина кратчайшей уникальной подпоследовательности, вы можете вернуться назад, чтобы напечатать подпоследовательность.

Ответ 3

Вы должны использовать модифицированную структуру Trie, вставить строки в trie так, чтобы:

Foo-bar-on
   -t
bar-stool
   -foo

Остальное просто, просто выберите правильный сжатый node [0] char

Что Дерево Radix должно помочь