Fişierul intrare/ieşire:shiroeseq.in, shiroeseq.outSursăAGM 2019, runda nationala
AutorTamio-Vesa NakajimaAdăugată dextreme77Patrick Sava xtreme77
Timp execuţie pe test6 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/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 0tn - 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

  • 1T10
  • 1|S|50.000
  • 1|P1| + ... + |PK|50.000

Exemplu

shiroeseq.inshiroeseq.out
2
ababab
2
ab
abab
abcaxa
3
a
yyy
ax
6
6
1
2
3
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?