Дадени са текст и речник (крайно множество от думи). Задачата е да се намерят позициите на всички срещания в текста на думи от речника. Алгоритъмът на Ахо—Корасик решава тази задача и се явява обобщение на алгоритъма на Кнут—Морис—Прат за търсене на една дума в текст.
Алгоритъмът се състои от две части. Първата е построяването на ориентиран граф по дадения речник, а втората е съвместното прочитане на текста и обхождане на графа, при което графът се използва подобно на краен автомат. Значително по-интересна е първата част.
Строим граф с три вида ребра.
Ребрата от първия вид образуват дърво на представките от думите в речника. То съдържа по един връх за всяка представка на всяка дума от речника, в това число самите думи и празната дума ε, която се явява начален връх на графа. Тези ребра ще наричаме ребра напред.
Вторият вид ребра сочат от всеки връх на представка към върха на най-дългата ѝ наставка. Ако един от върховете отговаря например на думата "орех", трябва да направим ребро към върха, който отговаря на най-дългата от наставките "рех", "ех", "х" и ε. Тези ребра ще наричаме ребра назад.
Третият вид ребра сочат от всеки връх на представка към върха на най-дългата ѝ наставка, която е част от речника (възможно е да няма такава наставка).
Построяването на ребрата напред определя всички върхове на графа. То става чрез последователното прочитане на всяка дума от речника. Четейки буква от дума, се движим в графа по ребрата напред. Ако стигнем до връх, от който не можем да продължим, създаваме нов връх и ребро напред към него.
За построяването на ребрата назад са важни следните наблюдения. Първо, за всяко ребро назад (u ; v) върхът u е на по-голямо разстояние от началото, отколкото v. Второ, кандидатите за v намираме, като се движим по ребрата назад от родителя на u и проверяваме дали от краищата им излиза ребро напред със същата буква като буквата на реброто напред, влизащо в u. Следвайки тези съображения, можем да намерим всички ребра назад с едно обхождане в ширина.
Последния вид ребра можем да построим, като се движим по ребрата назад и проверяваме дали съответният връх отговаря на дума от речника.
След като сме построили графа, прочитаме текста по следния начин. Четем знак и ако има ребро напред с този знак, минаваме по реброто. Ако няма такова ребро, се придвижваме по ребрата назад и отново проверяваме за ребро напред. Продължаваме да изследваме ребрата назад, докато открием нужното ребро напред или стигнем до началния връх и се окаже, че няма подходящо ребро напред.
Ако върхът, в който сме пристигнали, отговаря на дума от речника, отпечатваме я. Освен това, ако има нейни наставки, които също са от речника (тоест ако съществуват ребра от третия вид), отпечатваме и всички тях.
Тези действия се повтарят, докато стигнем до края на текста.
Псевдокодът тук е променена версия на този от книгата Ефективно търсене в текст от Алфред Ахо и Маргарет Корасик.
CreatePrefixTree(dictionary[1..n]: списък от думи)
1 newNode ← 1
2 for string in dictionary do
3 AddWord(string)
AddWord(string=a1..an: дума от речника)
1 node ← 0
2 i ← 1
3 while goto(node, ai) = t do
4 node ← goto(node, ai)
5 i ← i + 1
6 while i < n do
7 goto(node, ai) ← newNode
8 newNode ← newNode + 1
9 i ← i + 1
10 output(node) ← string
CreateFailureTransitions(goto; output)
1 create empty queue Q
2 for each goto(0, a) = node do
3 failure(node) ← 0
4 Enqueue(Q, node)
5 while not IsEmpty(Q) do
6 r ← Dequeue(Q)
7 for each goto(r, a) = node do
8 Enqueue(Q, node)
9 f ← failure(r)
10 while goto(f, a) is undefined and f ≠ 0 do
11 f ← failure(f)
12 if goto(f, a) = t do
13 failure(node) ← goto(f, a)
14 else do
15 failure(node) ← 0
16 output(node) ← output(node) ∪ output(failure(node))
PatternMatching(text=a1..an: низ, в който търсим думи от речника; goto; failure; output)
1 node ← 0
2 for i ← 1 to n do
3 tnode ← node
4 while goto(tnode, ai) is undefined and tnode ≠ 0 do
5 tnode ← failure(tnode)
6 if goto(tnode, ai) = t do
7 node ← t
8 else do
9 node ← 0
10 if output(node) ≠ empty do
11 print i
12 print output(node)
За функцията PatternMatching можем да направим следните наблюдения: за едно изпълнение на цикъла се прави най-много един преход по ребро напред, а общият брой преходи по ребра назад не е по-голям от общия брой преходи по ребра напред. Следователно функцията прави не повече от 2n прехода, където n е дължината на текста. Това са всички преходи с изключение на тези за извеждането на думите. Ето защо сложността на тази функция е O(n + z), където z е броят на срещнатите думи от речника.
Функцията AddWord има линейна времева сложност, затова времевата сложност на CreatePrefixTree е линейна спрямо сбора от дължините на думите от речника.
За функцията CreateFailureTransitions можем да направим разсъждения, подобни на тези за функцията PatternMatching: командата "f ← failure(f)" се изпълнява не повече пъти от сбора на дължините на думите от речника.
Следователно построяването на графа изисква време O(m), където m е сборът от дължините на думите от речника.