Problem statement: zenit13ckh
H: Simon the Sorcerer |
35 bodov | Časový limit: 4000 ms |
Simonovi sa s pomocou umelej brady konečne podarilo dostať do trpasličej nory. Ako je známe, trpaslíci okrem
pitia piva dolujú v útrobách hôr cenné kamene, ktoré by sa dali v meste speňažiť. Miestnosť, kde sa
drahokamy ťažia je ale strážená prísne vyzerajúcim trpaslíkom.
Na vstup do baníckej časti nory je potrebné strážnikovi povedať heslo. Simon začul časť konverzácie
medzi trpaslíkom vstupujúcim do bane a strážami. Na základe počutého vie, že heslo je jedno slovo a
tiež začiatky niektorých slov, ktoré by ním mohli byť. Viac sa mu nepodarilo začuť, pretože z bane
ho rušil hluk ťažobných nástrojov a z miestnosti vedľa ho rušil spev opitých trpaslíkov, ktorí zrovna
nemajú službu.
Simonovi sa podarilo v nore nájsť výkladový slovník trpasličieho jazyka. Tento jazyk je podobný
jazyku ľudí, ale jeho slovná zásoba je mierne odlišná.
Rád by pre každý možný začiatok hesla vedel, koľko slov trpasličieho jazyka ním začína.
Na prvom riadku vstupu je počet slov v trpasličom jazyku N (podľa nájdeného slovníka).
Na každom z ďalších
N riadkoch je jedno z týchto slov. Tieto slová sú dlhé aspoň jeden a najviac 50 znakov a
pozostávajú len z malých písmen anglickej abecedy. Môžete predpokladať, že sú všetky rôzne.
Na ďalšom riadku je počet možných začiatkov hesla M. Na zvyšných M riadkoch sú tieto začiatky.
Všetky sú neprázdne, pozostávajú z najviac 50 znakov malej anglickej abecedy a sú rôzne.
Platí 0 ≤ N ≤ 500,000 a 1 ≤ M ≤ 500,000.
Pre každého kandidáta w vypíšte na výstup jeden riadok s jedným číslom: počet
slov v trpasličom jazyku takých, že w je ich prefixom. Platí, že w je prefixom v, ak existuje
(aj prázdne) slovo u také, že wu = v. Napríklad slovo zenit má ako prefix prázdne slovo
a slová z, ze, zen, zeni a zenit.
Okrem vzorového prístupu existujú aj pomalšie riešenia, ktoré
získajú primeraný počet bodov. Na testovači máte okrem tu
uvedených vstupov aj jeden väčší. V tejto úlohe neodporúčame použiť Python (negarantujeme, že môže získať plný počet bodov).
Pamäťový limit v tejto úlohe je 2 GB.
>
Príklady:
| |
4
antikvariat
antarktida
mantinel
anicka
3
ant
mantinely
antikv
|
| |
| |
4
aabb
aaabb
abb
aaaab
4
aab
a
aa
aabb
|
| |