Разбор добавил Denis Galeev

Пусть нам заданы два шаблона S[1..M] и T[1..N]. Обозначим через F(i, j) любую строку минимальной длины, удовлетворяющую шаблонам S[1..i] и T[1..j]. Если такой строки нет, то в F(i, j) будет стоять специальная пометка, говорящая об этом. Вычисляем значения F(i, j) в порядке возрастания i, а при равных i – в порядке возрастания j. Возможны следующие ситуации (мы считаем, что i, j > 0, разбор граничных случаев проведите самостоятельно): S[i] и T[j] – буквы. Если они совпадают, то в качестве F(i, j) берем значение F(i-1, j-1) с дописанной в конце этой буквой. Если в F(i-1, j-1) стоит пометка «строки не существует», то аналогичная пометка ставится и в F(i, j). В случае несовпадения букв S[i] и T[j] нужная строка также не существует. S[i] и T[j] – буква и символ ? или два символа ?. Поступаем точно так же, как и в предыдущей ситуации, однако случая несовпадения букв из-за наличия ? здесь быть не может. S[i] – символ *, T[j] – буква или символ ?. Выбираем наиболее короткое среди значений F(i-1, j) и F(i, j-1) с дописанной к нему буквой T[j] (или любой буквой, если T[j] есть символ ?). S[i] – буква или символ ?, T[j] – символ *. Поступаем аналогично ситуации 3. S[i] и T[j] – два символа *. В этой ситуации в качестве F(i, j) берем наиболее короткое из значений F(i, j-1) и F(i-1, j).