Fişierul intrare/ieşire:ahocorasick.in, ahocorasick.outSursăArhiva educationala
AutorArhiva EducationalaAdăugată deS7012MYPetru Trimbitas S7012MY
Timp execuţie pe test0.1 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

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.inahocorasick.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

Aplicaţii

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content