h2. Solutie

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

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':

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