Să considerăm două şiruri de caractere s1 şi s2, având aceeaşi lungime N.
Distanţa Hamming dintre cele două şiruri este H(s1, s2) = numărul de poziţii i (0<=i<N) pentru care s1[i]!=s2[i].
De exemplu, H("motan", "saten")=3.
Un dezavantaj îl constituie faptul că pentru a utiliza distanţa Hamming cele două şiruri trebuie să aibă aceeaşi lungime. Pentru a elimina acest dezavantaj, am putea completa şirul mai scurt, adăugând la sfârşit un caracter care nu apare în niciunul dintre cele două şiruri (de exemplu, *).
Egalizând astfel lungimile celor două şiruri este posibil ca între două şiruri foarte asemănătoare să se obţină o distanţă Hamming foarte mare.
De exemplu H("uimit","umil*")=4.
Dacă am insera * după caracterul u, atunci H("uimit","u*mil")=2
Prin urmare intenţionăm să inserăm optimal* în cele două şiruri astfel încât:
lungimile şirurilor obţinute să fie egale;
distanţa Hamming dintre şirurile obţinute să fie minimă;
lungimile şirurilor obţinute să nu depăşească 10000 de caractere.
Cerinţă
Scrieţi un program care să insereze optimal caractere * în şirurile s1, s2.
Date de intrare
Fişierul de intrare distsir.in conţine două linii. Pe prima linie se află şirul s1, iar pe a doua linie se află şirul s2.
Date de ieşire
Fişierul de ieşire distsir.out va conţine 3 linii. Pe prima linie va fi scrisă distanţa Hamming minimă, obţinută după inserarea caracterelor *. Pe linia a doua va fi scris şirul obţinut din s1 după inserarea caracterelor *, iar pe linia a treia va fi scris şirul obţinut din s2 după inserarea caracterelor *.
Restricţii
Şirurile s1 şi s2 sunt formate din cel mult 2000 de caractere (litere mari, litere mici, cifre, spaţii, semne de punctuaţie).
Dacă există mai multe variante de a obţine distanţa Hamming minimă, afişaţi una dintre acestea.