informatics.mccme.ru

http://informatics.mccme.ru/moodle/mod/ … pterid=217

Задачу можно решить методом Динамического программирования.
Допустим что нибудь -
F(i,j) - минимальное кол-во символов которое потребуется что бы забить шаблон первой строки по i-ый символ,
а так же забить этими же символами шаблон второй строки по j-ый символ.

Тогда допустим мы сейчас стоим на состоянии F(i,j),какие у нас есть варианты :
#1. (S1(i) = '?' ,S2(j) = буква) или (S1(i) = буква ,S2(j) = '?') или (S1(i) = '?' ,S2(j) = '?') или
(S1(i) = буква, S2(j) - буква,S1(i) = S2(j)),тогда F(i+1,j+1) = min(F(i+1,j+1),F(i,j)+1);
#2. (S1(i) = '*', S2(j) = '?' или буква),тогда перебираем for q = j+1 .. length(S2) -> F(i,q)=min(F(i,q),F(i,j)+T2(j,q)). (T1(i,j),T2(i,j) - кол-во не '*' в подстроке S1[i..j],S2[i..j] соответственно)
#3. (S1(i) = '?' или буква, S2(j) = '*'),тогда перебираем for q = i+1 .. length(S1) -> F(q,j)=min(F(q,j),F(i,j)+T1(i,q)).

То есть мы моделируем текущую ситуацию,и смотрим что можно поставить в текущий момент.
Ответ можно восстановить по предкам.

Сложность решения ~O(Len^3). (Для Len <= 80 это очень быстро).
Если бы были более большие ограничения,то можно было бы рассказать и идею быстрее,но это не нужно для данной задачи.

Прошу прощения если где допустил ошибку,пишу сонный