Pracsiu Dan (dnprx) O pereche de șiruri de caractere S și T, formate doar din literele A, B și C, este egalabilă dacă șirurile pot deveni egale după o transfomare constând din aplicarea unei succesiuni formate din 0 sau mai multe operații. O operație constă din inserarea sau ștergerea din unul dintre șiruri a uneia dintre subsecvențele: AAA, BBB, CCC, ABC sau BAC. Atât inserarea, cât și ștergerea se pot realiza de pe orice poziție. În urma unei operații este posibil ca șirul rezultat să devină vid.
Cerința
Pentru o succesiune dată de perechi de șiruri, să se determine, pentru fiecare pereche, dacă este egalabilă.
Date de intrare
Fișierul de intrare segalt.in conține pe prima linie numărul Q de perechi. Pentru fiecare pereche sunt specificate cele două șiruri, pe linii diferite.
Date de ieșire
Fișierul de ieșire segalt.out va conține Q linii. Pe cea de a i-a linie va fi scris mesajul DA dacă cea de a i-a pereche din fișierul de intrare este egalabilă, respectiv mesajul NU, în caz contrar.
Restricții și precizări
1 ≤ Q ≤ 10.0001 ≤ lungimea maximă a unui șir (notată cu Nmax) ≤ 175.000- Suma lungimilor șirurilor din toate perechile (notată cu
S) este cel mult350.000 - Pentru 15 puncte,
S ≤ 3000și dacă perechea este egalabilă, există o transformare cu cel mult o operație - Pentru 23 de puncte,
S > 3000și dacă perechea este egalabilă, există o transformare cu cel mult o operație - Pentru 22 de puncte,
Nmax ≤ 8, S ≤ 800și dacă perechea este egalabilă, există o transformare cu cel mult două operații - Pentru 40 de puncte, fără restricții suplimentare.
Exemplu:
segalt.in
2 ABC CCC AABBACCBCCBC CCCCCCCCC
segalt.out
DA NU
Explicație
Pentru prima pereche, secvența ABC din primul șir poate fi ștearsă, apoi se inserează secvența CCC. Pentru a doua pereche se poate demonstra că nu există nicio transformare în urma căreia șirurile să devină egale.