Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | ahocorasick.in, ahocorasick.out | Sursă | Arhiva educationala |
| Autor | Arhiva Educationala | Adăugată de |  Petru Trimbitas •S7012MY |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Aho-Corasick
Se dă un şir A şi un dicţionar format din n cuvinte. Să se precizeze pentru fiecare cuvânt, i, numărul de apariţii din şirul A.
Date de intrare
Fişierul de intrare ahocorasick.in conţine pe prima linie şirul A. Pe a doua linie se află n, numărul de cuvinte din dicţionar. Următoarele n linii conţin fiecare câte un cuvânt din dicţionar.
Date de ieşire
Fişierul de ieşire ahocorasick.out conţine n linii pe fiecare aflându-se numărul de apariţii ale cuvântului i din şirul A.
Restricţii
- Şirurile conţin doar caractere mici ale alfabetului englez.
- 1 ≤ Lungimea lui A ≤ 1 000 000
- 1 ≤ Lungimea unui cuvânt ≤ 10000
- 1 ≤ n ≤ 100
Exemplu
| ahocorasick.in | ahocorasick.out |
|---|---|
| abcabacaa 6 a ab bc bca c caa | 5 2 1 1 2 1 |
Solutie
O rezolvare bazată pe kmp obţine 55 puncte. O sursă demonstrativă se găseşte aici
Soluţia eficientă foloseşte un automat de potrivire cunoscut sub numele de Aho-Corasick . O descriere a acestui algoritm aici şi aici
Acesta construieşte din cuvintele din dicţionar un trie care mai conţine pentru fiecare nod x o muchie de nepotrivire care duce intr-un nod cu proprietatea că este cel mai lung prefix al cuvintelor care e şi sufix al lui x. O sursă demonstrativă se găseşte aici
