Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | conexiuni.in, conexiuni.out | Sursă | Algoritmiada 2010, Runda Finala |
| Autor | Adrian Airinei | Adăugată de |  Airinei Adrian •astronomy |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Conexiuni
Recent s-a descoperit faptul ca ar putea exista anumite conexiuni intre civilizatiile extraterestre si sirurile de caractere ale alfabetului englez. Regele planetei va roaga sa investigati aceste conexiuni. El va pune la dispozitie doua siruri A si B care contin numai litere ale alfabetului englez (de la a la z) si va roaga sa ii spuneti pentru fiecare subsecventa din sirul A de cate ori apare aceasta in sirul B. Fie NRi,j numarul de aparitii ale subsecventei aflate intre pozitiile i si j in sirul A. Regele planetei va roaga sa calculati pentru fiecare pereche (i, j) valoarea NRi,j XOR i XOR (j+1) si sa faceti suma acestor valori.
Date de intrare
Fişierul de intrare conexiuni.in contine pe prima linie doua numere separate de un singur spatiu, N si M reprezentand lungimea sirului A, respectiv a sirului B. Pe urmatoarea linie se afla un sir de N caractere ce reprezinta sirul A, iar pe ultima linie un sir de M caractere ce reprezinta sirul B.
Date de ieşire
În fişierul de ieşire conexiuni.out veti afisa un singur numar, suma valorilor ceruta de Regele planetei.
Restricţii
- 1 ≤ N ≤ M ≤ 5000
- Operatorul XOR are aceiasi semnificatie cu operatorul ^ din C++ sau xor din Pascal
Exemplu
| conexiuni.in | conexiuni.out |
|---|---|
| 5 6 abaaa ababaa | 73 |
Explicaţie
Subsecventa aba din sirul A care se afla intre pozitiile 1 si 3 apare de doua ori in sirul B. Prima oara o gasim intre pozitiile 1 si 3 ale sirului, iar a doua oara intre pozitiile 3 si 5. Astfel va trebui sa adunam la rezultat valoarea 2 XOR 1 XOR 4.
