Državno natjecanje 2018. godine za 1. i 2. razred Srednje Škole - 1. zadatak - 2. dan

Slavica želi svojoj najfrendici Mirjani poslati poruku na mobitelu, međutim pokvarila joj se tipkovnica na dodir. Srećom, u copy/paste spremniku Slavičinog mobitela ostala je spremljena stara poruka A. Slavica želi novu poruku B napraviti na sljedeći način:

• Nova poruka u Slavičinom mobitelu je na početku prazna
• Sada, Slavica može K puta zalijepiti na kraj nove poruke poruku A, gdje je K prirodni broj. Tako na primjer, ako je poruka A ‘oskar’ tada nova poruka na kraju ovog poteza može biti ‘oskar’ ili ‘oskaroskar’ ili ‘oskaroskaroskar’ i tako dalje.
• U zadnjem koraku Slavica može izbrisati nula, jedan ili više znakova na proizvoljnim pozicijama u poruci.

Primjerice, ako je spremljena poruka A jednaka ‘oskar’, a tražena poruka B je ‘rosa’ tada Slavica može pomoću dvije kopije poruke A dobiti poruku ‘oskaroskar’, iz koje do tražene poruke B može doći brisanjem prva četiri slova poruke (‘oska’) te slova ‘k’ i ‘r’ na 8. i 10. poziciji.

Napišite program koji će za zadane poruke A i B odrediti najmanji prirodni broj K tako da Slavica može od poruke A dobiti poruku B opisanim postupkom i da se u drugom koraku postupka A zalijepi točno K puta.

ULAZNI PODACI

U prvom redu ulaza nalazi se poruka A, dok se u drugom redu nalazi poruka B. Obje poruke će se sastojati samo od malih slova engleske abecede te neće imati više od 100 000 znakova.

IZLAZNI PODACI

U prvi i jedini red izlaza ispišite jedan prirodni broj najmanji broj K iz teksta zadatka. Napomena: Test podaci će biti takvi da rješenje uvijek postoji.

PRIMJERI TEST PODATAKA

ulaz

oskar
rosa

izlaz

2

ulaz

mirko
mirmirkoko

izlaz

3

ulaz

aaaaab
bbbbbb

izlaz

6