Fişierul intrare/ieşire:balbaiala.in, balbaiala.outSursăAlgoritmiada 2018 Runda Finala
AutorCosmin Silvestru Negruseri, Eugenie Daniel PosdarascuAdăugată deklamathixMihai Calancea klamathix
Timp execuţie pe test0.7 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/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.inbalbaiala.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?