Aho-Corasick

ahocorasick

== include(page="template/taskheader" task_id="ahocorasick") ==

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

Poveste şi cerinţă...

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

Fişierul de intrare $ahocorasick.in$ ...

h2. 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$.

În fişierul de ieşire $ahocorasick.out$ ...

h2. 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$

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. ahocorasick.in |_. ahocorasick.out |

| abcabacaa
6
a
ab
bc
bca
c
caa
| 5
2
1
1
2
1

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|

h2. Solutie

h3. Explicaţie

O rezolvare bazată pe 'kmp':problema/strmatch obţine 55 puncte. O sursă demonstrativă se găseşte 'aici':job_detail/658859?action=view-source

...

Soluţia eficientă foloseşte un automat de potrivire cunoscut sub numele de $Aho-Corasick$ . O descriere a acestui algoritm 'aici':http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm şi 'aici':https://docs.google.com/viewer?a=v&pid=explorer&chrome=true&srcid=1puSAKcZT_Y3fz8MmYGOaa-QRJuyX1TB-gXO-Fl9dbE7L9sq2G-IAKKP8u0Fg&hl=en_US
!  problema/ahocorasick?Aho_Corasick_Concept.PNG !
 
p<>. Acesta construieşte din cuvintele din dicţionar un 'trie':problema/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':job_detail/658871?action=view-source
 
h2. Aplicaţii
 
* 'Virus':problema/virus
* 'Strigat':problema/strigat
* 'Obscene Words Filter':http://acm.timus.ru/problem.aspx?space=1&num=1269
 
 
== include(page="template/taskfooter" task_id="ahocorasick") ==

== include(page="template/taskfooter" task_id="ahocorasick") ==
 

6878