Fişierul intrare/ieşire:ultron.in, ultron.outSursăBaraj Yakuția 2015
AutorAlexandru ValeanuAdăugată deAlexandruValeanuAlexandru Valeanu AlexandruValeanu
Timp execuţie pe test1.5 secLimită de memorie32768 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Ultron

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.

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.
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.

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.

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.

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

Exemplu

ultron.inultron.out
aa
abaa
8
ultron.inultron.out
aab
acaabada
32
ultron.inultron.out
aab
acaabazaaab
64

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici