!>problema/ultron?rsz_ultron.jpg!
$**SPOILERS!**$
În încercarea supremă de a salva lumea și de a obține pacea pe Pământ, Tony Stark și Bruce Banner au descoperit o formă superioară de inteligență, aflată în piatra din sceptrul lui Loki. Această formă superioară, integrată desigur într-un calculator, dintr-un mic accident, a înțeles că singura modalitate de a salva planeta este distrugerea oamenilor.
În acest scop, noul adversar al echipei conduse de Nick Fury a creat o bombă ce urma să distrugă fiecare om - bombă programată, din fericire, într-un limbaj cunoscut de Stark.
Acesta, după multe încercări și ajutat de prietenul său, J.A.R.V.I.S., a reușit să recreeze codul sursei scrise de Ultron. Cum nu este tocmai convins de reușita sa, Tony vă roagă să-l ajutați să afle cât de mult seamănă codul său cu codul lui Ultron.
În încercarea supremă de a salva lumea și de a obține pacea pe Pământ, Tony Stark și Bruce Banner au discoperit o formă superioară de inteligență, aflată în piatra din sceptrul lui Loki. Această formă superioară, integrată desigur într-un calculator, dintr-un mic accident, a înțeles că singura modalitate de a salva planeta este distrugerea oamenilor.
În acest scop, noul adversar al echipei conduse de Nick Fury a creat o bombă ce urma să distrugă fiecare om, bomba programată, din fericire, într-un limbaj cunoscut de Stark.
Acesta, după multe încercări și ajutat de prietenul său, J.A.R.V.I.S., a reușit (afirmând plin de modestie) să recreeze codul sursei scrise de Ultron. Cum nu este tocmai convins de reușita sa, Tony vă roagă să-l ajutați să afle cât de mult seamănă codul său cu codul lui Ultron.
Mai formal, un cod este un șir format din litere mici ale alfabetului latin. Asemănarea dintre cele două coduri (șiruri) este egală cu cel mai lung prefix comun al celor două.
Tony vă roagă să aflați pentru fiecare subsecvență (zonă contiguă) a codului său, asemănarea dintrea aceasta și codul sursei scrise de Ultron.
Mai formal, un cod este un șir format din litere mici ale alfabetului latin. Asemănarea dintre cele două coduri(șiruri) este egală cu cel mai lung prefix comun al celor două.
Tony vă roagă să aflați pentru fiecare subsecvență(zonă contiguă) a codului său, asemănarea dintrea aceasta și codul sursei scrisă de Ultron.
Pentru a nu încărca serverul de la Stark Industries cu prea multe numere trebuie să afișați doar suma tuturor asemănărilor.
h2. Date de intrare
Fișierul de intrare $ultron.in$ conține pe prima linie codul bombei (un șir de lungime [$N$]) iar pe cea de-a doua codul (un șir de lungime [$M$]) scris de Tony Stark.
Fișierul de intrare $ultron.in$ conține pe prima linie codul bombei(un șir de lungime [$N$]) iar pe cea de-a doua codul(un șir de lungime [$M$]) scris de Tony Stark.
h2. Date de ieșire
Fișierul de ieșire $ultron.out$ va conține o singură linie pe care va fi afișat numărul cerut.
În fișierul de ieșire $ultron.out$ va conține o singură linie pe care va fi afișat numărul cerut.
h2. Restricții
* $1 ≤ N, M ≤ 2.000.000$
* Pentru $20%$ din punctaj se garantează că $N, M ≤ 2.000$
* Pentru $50%$ din punctaj se garantează că $N, M ≤ 100.000$
* Pentru $80%$ din punctaj se garantează că $N, M ≤ 500.000$
* $1 ≤ [$N$], $M$ ≤ 2.000.000$
* $Pentru 20% din punctaj se garantează că [$N$], $M$ ≤ 2.000$
* $Pentru 50% din punctaj se garantează că [$N$], $M$ ≤ 100.000$
* $Pentru 80% din punctaj se garantează că [$N$], $M$ ≤ 500.0000$
h2. Exemplu
table(example).
|_. ultron.in |_. ultron.out |
| aa
abaa
abaa
| 8
|
table(example).
|_. ultron.in |_. ultron.out |
| aab
acaabada
acaabada
| 32
|
table(example).
|_. ultron.in |_. ultron.out |
| aab
acaabazaaab
acaabazaaab
| 64
|
h3. Explicație pentru primul test
Subsecvențele lui abaa sunt: a, ab, aba, abaa, b, ba, baa, a, aa, a.
Asemănarea este: 1, 1, 1, 1, 0, 0, 0, 1, 2, 1.
Suma lor este: 8.
Subsecvențele lui abaa sunt: a, ab, aba, abaa, b, ba, baa, a, aa, a;
Asemănarea este: 1, 1, 1, 1, 0, 0, 0, 1, 2, 1;
Suma lor este: 8;
