Это в основном проблема сопоставления регулярных выражений.
Сначала избавимся от условия «последний символ совпадает». Мы хотим свести задачу к «простой проблеме числа равных подпоследовательностей без каких-либо условий».
Предположим, что 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