| Fişierul intrare/ieşire: | balbaiala.in, balbaiala.out | Sursă | Algoritmiada 2018 Runda Finala |
| Autor | Cosmin Silvestru Negruseri, Eugenie Daniel Posdarascu | Adăugată de |  Mihai Calancea •klamathix |
| Timp execuţie pe test | 0.35 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Balbaiala
Fie un şir de caractere S. Numim bâlbâială de ordin k a lui S şirul obţinut prin multiplicarea fiecărui caracter al lui S de exact k ori. Spre exemplu, bâlbâiala de ordin 2 a şirului "andrei" este şirul "aannddrreeii", iar bâlbâiala de ordin 3 a şirului "ana" este şirul "aaannnaaa".
Fie un şir de caractere A şi Q şiruri de caractere B1, B2, .. BQ. Pentru fiecare şir B, dorim să aflăm bâlbâiala de ordin maxim a respectivului şir care apare ca subşir în şirul A. Spre exemplu, pentru A = "onomatopee" şi B = "oe", ordinul maxim al bâlbâielii este egal cu 2, iar pentru B' = "z", ordinul maxim al bâlbâielii este egal cu 0.
Date de intrare
Fişierul de intrare balbaiala.in contine pe prima linie numerele naturale N (marimea sirului A) si Q (numarul de siruri Bi), pe a doua linie sirul A de caractere, iar pe urmatoarele Q linii sirurile Bi.
Date de ieşire
În fişierul de ieşire balbaiala.out se vor afla Q linii, pe a i-a dintre ele fiind un numar natural reprezentand ordinul maxim al bâlbâielii sirului Bi care sa apara ca subsir in sirul A.
Restricţii
- Suma lungimilor celor Q query-uri este mai mica sau egala cu 300.000
- Pentru 20 de puncte, 1 ≤ N, Q ≤ 100
- Pentru 40 de puncte, 1 ≤ N, Q ≤ 5.000
- Pentru 70 de puncte, 1 ≤ N ≤ 30.000 si 1 ≤ Q ≤ 40.000
- Pentru toate punctele, 1 ≤ N, Q ≤ 100.000
Exemplu
| balbaiala.in | balbaiala.out |
|---|---|
| 13 3 abbbaababbaaa ab ba aba | 3 4 3 |
Explicaţie
- ab - Bâlbâiala de ordin 3, aaabbb, apare ca subsir in A, dar cea de ordin 4 nu
- ba - Bâlbâiala de ordin 4 apare ca subsir in A, dar cea de ordin 5, bbbbbaaaaa, nu
- aba - Bâlbâiiala de ordin 3, aaabbbaaa, apare ca subsir in A, dar cea de ordin 4 nu
