| Fişierul intrare/ieşire: | shiroeseq.in, shiroeseq.out | Sursă | AGM 2019, runda nationala |
| Autor | Tamio-Vesa Nakajima | Adăugată de |  Patrick Sava •xtreme77 |
| Timp execuţie pe test | 3 sec | Limită de memorie | 256000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Shiroeseq
Activitatea nouă a lui Shiroe implică încercarea de a detecta anumite fraze memorabile în unele fluxuri de date criptate.
Mai exact, lui i se dă un şir S şi un set de K pattern-uri Pi (cu |Pi| ≤ |S|), toate conţinând numai litere mici. Pentru fiecare pattern P, spunem că un substring
S' din S "conţine puternic" P dacă şi numai dacă fiecare subsecventa S'' de lungime |P| din S' este o anagrama a lui P. Pentru a afla cât de des apare fiecare pattern în S, Shiroe trebuie să găsească, pentru fiecare Pi, lungimea lui S'i, cea mai lungă subsecventa a lui S care "conţine puternic" Pi.
Reţineţi că un substring al unui şir S = <s1, ..., sn> este un alt şir P = <p1, ..., pk> astfel încât să existe o poziţie t (cu 0 ≤ t ≤ n - k) astfel încât s(t + x) = px pentru toate x ∈ {1, 2, 3, ..., k}.
Reţineţi că o anagramă a unui şir S este orice alt şir P care poate fi format din S prin permutarea caracterelor lui S.
Date de intrare
Fişierul de intrare shiroeseq.in contine pe prima linie T, numărul de teste.
Prima linie a unui test conţine S.
A doua linie a unui test conţine K.
Următoarele K linii ale fiecărui test conţin pattern-urile Pi, in ordine.
Date de ieşire
În fişierul de ieşire shiroeseq.out se afla răspunsurile pentru fiecare test în ordine.
Răspunsul pentru un test constă în K linii, fiecare dintre ele reprezentand lungimea substringului cerut pattern-ului respectiv.
Restricţii
- 1 ≤ T ≤ 10
- 1 ≤ |S| ≤ 50.000
- 1 ≤ |P1| + ... + |PK| ≤ 50.000
Exemplu
| shiroeseq.in | shiroeseq.out |
|---|---|
| 2 ababab 2 ab abab abcaxa 3 a yyy ax | 6 6 1 2 3 |
