Матч 6, Сравнение с шаблоном (WildCard)

Строка file содержит имя файла. Его необходимо преобразовать в строку pattern, которая может содержать символы-джокеры ‘?’ (один любой символ). Необходимо найти наименьшее количество операций вставки, удаления или переименования символа, выполнение которых преобразовывают file в pattern.

Класс: WildCardMatch

Метод: int minimalChanges(string file, string pattern)

Ограничения: file и pattern содержат от 1 до 50 символов ‘a’ – ‘z’, строка pattern может содержать символы-джокеры ‘?’.

Вход. Две строки file и pattern.

Выход. Наименьшее количество операций вставки, удаления или переименования символа, преобразовывающих file в pattern.

Пример входа

file	pattern
"abcd"	"bcd"
"aaaabbb"	"aa????b"
"asdjkhajksdhajksdh"	"asdjkhasdjk?"
"niceone"	"ieo?e"

Пример выхода

1

0

6

2

РЕШЕНИЕ

динамическое программирование

Пусть f[i][j] содержит наименьшее количество преобразований, которые переводят file[0..i] в pattern[0..j]. Для удобства кодирования допишем в начало обоих слов символ ‘0’. От этого искомое количество операций не изменится, однако число преобразований file[0..i] в pattern[0..j] будет храниться в f[i + 1][j + 1]. После дописывания нулей перед строками нулевым индексам массива f соответствуют пустые строки. f[0][0] = 0 соответствует тому, что для преобразования пустой строки в пустую требуется 0 операций. f[0][j] будет хранить наименьшее количество операций, переводящих пустую строку (“”) в pattern[0..j – 1]. Занесем во все ячейки массива f значение µ. Рассмотрим, как вычислить значение f[i + 1][j + 1] по известным f[i₁][j₁], 0 £ i₁ £ i, 0 £ j₁ £ j:

· если file[i] = pattern[j] или pattern[j] = '?', то f[i + 1][j + 1] = f[i][j];

· если i - ый символ file и j - ый символ pattern не совпадают, то возможно одно из трех преобразований. Причем производить следует то преобразование, после выполнения которого f[i + 1][j + 1] с наименьшим, а именно:

· если file[i] заменить на pattern[j], то f[i + 1][j + 1] = f[i][j] + 1;

· если символ file[i] удалить, то f[i + 1][j + 1] = f[i][j + 1] + 1;

· если символ pattern[j] вставить, то f[i + 1][j + 1] = f[i + 1][j] + 1;

Объединив приведенные условия, получим:

f[i + 1][j + 1] =

min( min( 1 + f[i][j + 1], 1 + f[i + 1][j]), (!((file[i] = = pattern[j]) || (pattern[j] = = ‘?’))) + f[i][j]),

f[0][0] = 0.

ПРОГРАММА

#include <cstdio>

#include <string>

#include <memory>

using namespace std;

int f[51][51];

class WildCardMatch

{

public:

int minimalChanges(string file, string pattern)

{

int i,j;

memset(f,63,sizeof(f));f[0][0] = 0;

file = "0" + file; pattern = "0" + pattern;

for(i=0;i<file.size();i++)

for(j=0;j<pattern.size();j++)

f[i+1][j+1] = min(min(1+f[i][j+1],1+f[i+1][j]),

(!((file[i] == pattern[j]) || (pattern[j] == '?')))+f[i][j]);

return f[file.size()][pattern.size()];

}

};