Codah ClubTrain. Submit. Improve.
Sign in
English
#0006FF

Razlika Stringova

Data su dva stringa - A i B (length(A) > length(B)) sastavljena od malih slova engleske abecede. Neki karakteri u stringu B su zamenjeni karakterom '?'.


Razlika izmedju dva stringa S1 i S2, iste duzine, je broj indeksa X tako da je S1[X] != S2[X] .


Ukupna razlika izmedju stringova A i B je zbir razlika izmedju stringa B i svakog podstringa uzastopnih elemenata duzine length(B) stringa A.


Primer:
Ukupna razlika izmedju stringova "abataraba" i "baba" je jednaka
razlika("baba", "abat") [4] +
razlika("baba", "bata") [1] +
razlika("baba", "atar") [4] +
razlika("baba", "tara") [2] +
razlika("baba", "arab") [4] +
razlika("baba", "raba") [1] = 16


Zameniti karaktere '?' u stringu B tako da ukupna razlika bude najmanja moguca. Ukoliko ima vise resenja, ispisati leksikografski najmanje.


InputU prvom redu standardnog ulaza nalazi se string A. U drugom redu se nalazi string B. Duzina stringa A ce uvek biti veca od duzine stringa B.

OutputU prvom redu standardnog izlaza ispisati string B nakon zamenjivanja karaktera '?' tako da se dobija najmanja ukupna razlika izmedju stringova A i B. U drugom redu standardnog izlaza ispisati najmanju ukupnu razliku izmedju stringova A i B.

Ogranicenja:
U 30 % primera ce biti: 1 <= length(B) < length (A) <= 1.000 i samo jedan karakter '?' u stringu B.
u 50% primera ce biti: 1 <= length(B) < length (A) <= 1.000
u 100% primera ce biti: 1 <= length(B) < length (A) <= 1.000.000



Ulaz:
abbcd
b?d


Izlaz:
bbd
4


Ulaz:
qwertytre
d???z


Izlaz:
detrz
20

Objasnjenje:
Stringovi koji daju ukupnu razliku 20 su (leksikografski od najmanjeg ka najvecem): detrz, dettz, drtrz, drttz, dttrz, dtttz, dwtrz, dwttz, dytrz, dyttz.



Ulaz:
abataraba
???


Izlaz:
aaa
10

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.