Количество равных подпоследовательностей двух строк S1 и S2 с совпадением последнего символа S1

Учитывая две строки S1 и S2 разной длины, каков эффективный подход к поиску количества равных подпоследовательностей как S1, так и S2 с совпадающим последним символом S1.

e.g)

S1 = айб

S2 = ахbxxb

В этом случае присутствуют две равные подпоследовательности,

 "b"  => S1[2],S2[2]
 "b"  => S1[2],S2[5]
 "ab" => S1[0],S2[0] and S1[2],S2[2]
 "ab" => S1[0],S2[0] and S1[2],S2[5]

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


string algorithm dynamic-programming
person Anantha Krishnan    schedule 11.04.2012    source источник
comment
Я не думаю, что это называется подпоследовательностью РЕДАКТИРОВАТЬ: не обращайте на меня внимания, это подпоследовательность   -  person Argote    schedule 11.04.2012
comment
@Argote, тогда что такое подпоследовательность?   -  person Anantha Krishnan    schedule 11.04.2012

Ответы (1)


arrow_upward
0
arrow_downward

Это в основном проблема сопоставления регулярных выражений.

Сначала избавимся от условия «последний символ совпадает». Мы хотим свести задачу к «простой проблеме числа равных подпоследовательностей без каких-либо условий».

Предположим, что S1="a1a2...anZ". Пусть S1'="a1a2...an". Предположим далее, что в S2 имеется N вхождений Z. Для каждого случая мы можем написать

Предположим, что в S2 есть N вхождений Z. Для каждого вхождения i мы можем написать S2i="b1b2...b kiZbki+1...". Предположим, что S2'="b1b2...bki". Теперь решите простую задачу для S1' и S2'i для каждого i из 1..N.

Теперь, как решить простую проблему?

Возьмите более короткую строку, скажем, S1. Давайте теперь напишем это "abc…t". Превратите его в ".*a?.*b?.*…t?.*". Это ваше регулярное выражение. Теперь вам нужно подсчитать, сколько существует способов, чтобы регулярное выражение соответствовало S2. Сопоставление может быть выполнено с помощью алгоритма на основе NFA.

Чтобы на самом деле подсчитать количество совпадений, нужно понять внутреннюю работу алгоритма сопоставления на основе NFA. Есть набор состояний, которые активны в любой момент. Государство может быть разделено на два, или два состояния могут объединиться. Состояние может умереть, если встретит неправильный символ. Таким образом, вы присваиваете начальному состоянию 1 балл. Когда штат разделяется, каждый новый штат наследует счет родителя. Когда два состояния сливаются, новое состояние получает сумму баллов. Когда штат умирает, его баллы сбрасываются.

Я не уверен, отличается ли это от того, что вы называете подходом динамического программирования. Существует до 2N совпадений, поэтому для некоторых входных данных это займет много времени.

Обновление: похоже, что также можно решить проблему «последние совпадения символов» напрямую, не сводя ее к простой проблеме. Предположим, что в S2 есть 2 вхождения Z: S2="ab…pZq…yZ". (В любом случае можно игнорировать все символы после последней буквы Z). Можно построить регулярное выражение из S2: ".*a?.*b?.*…p?.*(Z|Z?.*q?.*…y?.*Z)". Таким же образом обрабатываются и другие вхождения. По-видимому, избыточное регулярное выражение необходимо для поддержания правильного количества совпадений (а не только факта наличия совпадения).

person n. 1.8e9-where's-my-share m.    schedule 11.04.2012
comment
Вы уверены, что это проблема с регулярным выражением? никак не решить с DP? - person Anantha Krishnan; 11.04.2012