.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » siruri2

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
siruri2


Timp maxim de execuţie / test:
0.1s
Memorie totala disponibilă / stivă:
3MB / 1MB

Distanţa Levenshtein dintre două şiruri de caractere este egală cu numărul minim de operaţii necesare pentru a transforma primul şir în celălalt. Operaţiile permise sunt inserarea unui caracter, ştergerea unui caracter sau înlocuirea unui caracter cu un alt caracter.

Cerinţă

Cunoscând cele două şiruri de caractere, să se determine care este numărul minim de operaţii necesare pentru a transforma primul şir în cel de-al doilea şir.

Date de intrare

Fişierul de intrare siruri2.in conţine pe prima linie primul şir, iar pe următoarea linie se află cel de-al doilea şir.

Date de ieşire

Fişierul de ieşire siruri2.out va conţine o singură linie pe care va fi scris un număr natural reprezentând numărul minim de operaţii necesare pentru a transforma primul şir în cel de-al doilea şir.

Restricţii

• Fiecare şir are cel mult 500 de caractere cu codurile ASCII cuprinse între 32 şi 127.
• Nu se face distincţie între literele mici şi cele mari.

Exemple

siruri2.insiruri2.outExplicaţii
abacul barca 4 Asupra primului şir se execută următoarele operaţii:
− se şterge primul caracter a;
− se inserează un caracter r înainte de caracterul c;
− se înlocuieşte caracterul u cu a;
− se şterge caracterul l.

autor: Prof. Constantin Creţu
propunător: Prof. Emanuela Cerchez
Liceul de Informatică ″Grigore Moisil″
emanuela.cerchez@gmail.com
Probleme recomandate
De la OMI Iaşi 2010: fazanr, cadouri, bursa, meteo, muguri, balcon, jump, calorii
De acelaşi autor: meteo, cuvinte2, subtitrare, tabla, diferenta, cifre6
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, palind, joc, vikingi, rafturi, balaur, plimbare, party, pc, pioni, seif, iepuri, numere3, perm, ture, bilete, prop, ro, reduceri, cuburi, invest, cutie2, stalpi, nr2, judete, strict, auto2, tree, jobs, leaves, pstring, program, datorii, senzori, farfurii, joc1, barbie, ambigram, rlcs, cub1, bio, chimie1, otilia, pasune, remi, sir23, tren1, joc5, pachete, echipe, comb, agitatie, ivv, peste, pitici, pipe, shgraf, tabara1, stop, randuri, zidar, log, sant, produs, subsir, cover, bcast, emax, dist, mesaj1, imax, avere, asmax, raft, suma2, joc12, fni, nr4, join, transport, masina3, lsort, microvirus, fat, cafea, echipe1, anticip, bsir, diamant, petrom, evantai, spion, acolor, evo, bombo, lacusta, lant, team, pitici1, numere8, dep, stiva, subgeom, pviz, tir1, cabane, piramida1, mosia, cuvinte1, gaina, materom, sortari, turnuri, trans, politie, codul, dansatori, nkbiti, kperms, treegame, 123, jucarii, bradut, joc15, expozitie, text3, ic, echilibru, distsir, kmax, stalpi1, gaz, triunghi2, v2d, cuiburi, mine, orientare, activ, secvbiti, kcons, pokemon, ubergraf, left, acerc, autostrazi, kdist, select, cazare, fluviu, telecomanda, parcela, pion, subs, suma4, sirmax, bdotcom, viena, sablon2, telecab, ikebana, radare, hacker, obstacole, robotel, centrala, verigi, cds, wg, minusk, radioactiv, enigma, jb, efect, maxviz, ripstick, progresii, maxtri, combcuv, blis, subsiruri, mijloc, probleme, unuzero, palindrom1, minerale, speed, zmax, spider, cntgcd, interclasare, bus, pariuri, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
surse trimise | ajutor