GOV-təcrübə 3
Tərif. Eyni uzunluqda olan iki sətir arasındakı Hemming məsafəsi, bu sətirlərin fərqli simvollarının sayıdır.
Tərif. s mətnindən p şablonuna olan məsafə, s sətirinin uzunluğu |p| olan bütün alt sətirləri ilə p arasındakı Hemming məsafələrinin cəmidir.
Verilmişdir mətn s və şablon p. Bu iki sətirdən biri zədələnmiş ola bilər (bəzi simvollar naməlumdur), lakin hər ikisi eyni anda zədələnmiş deyil. Zədələnmiş sətiri elə bərpa etmək lazımdır ki, mətnin şablona olan məsafəsi mümkün qədər az olsun.
Giriş verilənləri
Birinci sətirdə n tam ədədi verilmişdir — mətnin s uzunluğu (1 ≤ n ≤ 100000). İkinci sətirdə mətn s boşluqla ayrılmış n tam qeyri-mənfi ədədlər şəklində verilmişdir. Üçüncü sətirdə m tam ədədi verilmişdir — şablonun p uzunluğu (1 ≤ m < n). Dördüncü sətirdə şablon p oxşar formatda verilmişdir. Müsbət ədədlər bu simvolların əlifbadakı nömrələrini, sıfır isə zədələnmiş simvolu göstərir. Simvolların nömrələrini göstərən ədədlər 100000-dən çox deyil.
Çıxış verilənləri
Birinci sətirdə mətni, ikinci sətirdə isə şablonu verin, zədələnmiş sətiri elə bərpa edin ki, sətirlər arasındakı məsafə mümkün qədər az olsun. Əgər bərpa üçün bir neçə üsul varsa, istənilənini verin.