Найти количество уникальных самых длинных общих подпоследовательностей

Question

Для 2 строк я хочу найти количество различных LCS. Я читал в вики о том, как печатать все LCS, но как проверить, что они различны? Хэш-таблица неосуществима, так как каждая моя входная строка может иметь длину 1500-2000 символов, поэтому максимальное количество LCS может быть 2000, выберите 1000

Answer 1

Как только вы найдете каждую подпоследовательность, вставьте их в ленивую версию trie .

Три страдает от потери памяти. Таким образом, вместо того, чтобы хранить значения до конца, разветвляйтесь только тогда, когда необходимо разрешить конфликты.

Например. Анна, приложения, Анна

Первоначально корневой узел будет содержать анну.

Когда вы пытаетесь вставить приложения, вы понимаете, что в корне уже есть строка, и, следовательно, создаете ветку в и пытаетесь поместить anna и приложения. Конфликт сохраняется до тех пор, пока вы не разделитесь на и na и ap ps.

В настоящее время дерево будет выглядеть так:

                                    a
                           (anna) n   p (apps)

Теперь, когда вы вставите anne, вы достигнете an и поймете, что существует конфликт, и разрешите его, добавив ветвь n , за которой следуют a и е ветви.

Финальная строка будет выглядеть так:

                                    a
                                  n   p (apps)
                                n
                       (anna) a  e (anne)

Answer 2

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

Answer 3

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