Rezolvare PBinfo #3392

Magazinul de cuvinte este un șir s ce constă in n litere mici ale alfabetului latin. Literele sunt vândute una câte una, de la stânga la dreapta. O persoană poate să cumpere orice prefix de litere din șirul s.
Sunt m prieteni, al i -lea dintre ei are numele t[i] . Fiecare dintre ei vrea să-și construiască numele din litere cumpărate de la magazin.

Cerința

Se cere să se determine numărul minim de litere (lungimea celui mai scurt prefix) de care are nevoie fiecare dintre prieteni pentru a-și construi numele.
Un nume poate fi construit dacă fiecare literă din nume este cumpărată într-o cantitate mai mare sau egală. E garantat că fiecare prieten poate să-și construiască numele folosind literele din șirul de caractere s. Valorile pentru prieteni sunt independente, prietenii nu-și pot imprumuta litere între ei.

Date de intrare

Fișierul de intrare magazin.in conține pe prima linie numărul n – lungimea șirului de caractere s . A doua linie conține sirul s ce constă în exact n litere mici ale alfabetului latin. A treia linie conține m – numărul de prieteni. Urmează m linii, pe fiecare fiind t[i] – numele prietenului i.

Date de ieșire

Fișierul de ieșire magazin.out va conține m linii. Pe linia i se va afla lungimea celui mai scurt prefix de litere din s pe care trebuie să-l cumpere prietenul i pentru a-și putea construi numele.

Restricții și precizări

• 1 ≤ n ≤ 200.000
• 1 ≤ m ≤ 50.000
• \( \sum\limits_{i=1}^m strlen(t[i]) ≤ 200.000 \)

Exemplu:

magazin.in

12
martiaunseed
5
marius
matei
marian
marti
andrei

magazin.out

9
10
8
5
12

Explicație

Primul prieten are nevoie de prefixul martiauns, de lungime 9, pentru a putea construi numele marius.

matei cumpără prefixul martiaunse de lungime 10. marian cumpără prefixul martiaun de lungime 8. marti cumpără prefixul marti de lugime 5, iar andrei cumpără prefixul martiaunseed de lungime 12.