Saat kita harus mencari ribuan pattern dalam satu text — misalnya database signature virus atau daftar kata sensitif — algoritma seperti KMP yang menjalankan satu pencarian per pattern menjadi O(k·(n + m)) untuk k pattern. Algoritma Aho-Corasick memangkas faktor k dengan membangun satu automaton dari semua pattern sekaligus, lalu melakukan single scan O(n + total matches). Algoritma ini menggabungkan trie (untuk menyimpan semua pattern) dan failure link mirip KMP (untuk melompat saat mismatch). Pada Chapter ini kita akan membangun trie pattern, membangun failure link via BFS, dan melakukan search yang menemukan semua occurrence semua pattern dalam satu pass.

Aturan: Trie + Failure Link #

Aho-Corasick membangun dua struktur:

  1. Trie dari semua pattern: gabungkan semua pattern menjadi satu trie. Path root→node = prefix dari satu atau lebih pattern. Node yang menandai akhir pattern memiliki daftar output.
  2. Failure link fail[u]: node terpanjang v sehingga path root→v adalah suffix dari path root→u. Mirip failure function KMP, tapi untuk trie.

Karena trie menggabungkan prefix yang sama di antara pattern, biaya preprocess O(Σ|P_i|) (jumlah total panjang semua pattern), bukan O(k · max|P_i|).

Build #

  1. Insert semua pattern ke trie. Setiap node akhir pattern menyimpan indeks pattern dalam list output.
  2. BFS untuk failure link: untuk anak root, fail = root. Untuk node v dengan parent u via karakter c:
    • Mulai dari f = fail[u].
    • Ikuti fail naik hingga menemukan node yang punya anak karakter c (atau mencapai root).
    • fail[v] = anak_c dari f (atau root bila tidak ada).
  3. Output inheritance: copy output dari fail[v] ke v. Ini menangkap pattern yang merupakan suffix dari pattern lain.

Telusuri text karakter per karakter. Mulai dari root. Untuk setiap T[i]:

  • Bila node saat ini punya anak T[i], maju ke anak tersebut.
  • Bila tidak, ikuti failure link hingga menemukan node dengan anak T[i] atau mencapai root.
  • Setelah update node, kumpulkan semua output dari node tersebut (sudah termasuk output turunan dari failure link).

Diagram di atas menunjukkan trie pattern {"he", "she", "his"}. Failure link SHE → HE karena suffix "he" dari "she" adalah juga prefix pattern "he". Saat text "she" selesai dicocokkan, kita otomatis juga menemukan "he" tanpa scan ulang.

Kode: Aho-Corasick Lengkap #

cpp 
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <queue>

struct ACNode {
    std::unordered_map<char, int> children;
    int fail = 0;          // failure link
    std::vector<int> out;  // indeks pattern yang berakhir di node ini
};

struct AhoCorasick {
    std::vector<ACNode> nodes;
    std::vector<std::string> patterns;

    AhoCorasick() {
        nodes.push_back(ACNode{});  // root = node 0
    }

    void add_pattern(const std::string& p) {
        int cur = 0;
        for (char c : p) {
            auto it = nodes[cur].children.find(c);
            if (it == nodes[cur].children.end()) {
                int idx = static_cast<int>(nodes.size());
                nodes.push_back(ACNode{});
                nodes[cur].children[c] = idx;
                cur = idx;
            } else {
                cur = it->second;
            }
        }
        nodes[cur].out.push_back(static_cast<int>(patterns.size()));
        patterns.push_back(p);
    }

    void build_failure() {
        std::queue<int> q;
        // Anak root: fail = 0
        for (auto& kv : nodes[0].children) {
            nodes[kv.second].fail = 0;
            q.push(kv.second);
        }
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (auto& kv : nodes[u].children) {
                char c = kv.first;
                int v = kv.second;
                int f = nodes[u].fail;
                while (f != 0 && nodes[f].children.find(c) == nodes[f].children.end()) {
                    f = nodes[f].fail;
                }
                if (nodes[f].children.find(c) != nodes[f].children.end()
                    && nodes[f].children[c] != v) {
                    f = nodes[f].children[c];
                }
                nodes[v].fail = f;
                // Turunkan output dari node fail (suffix pattern)
                for (int pid : nodes[f].out) {
                    nodes[v].out.push_back(pid);
                }
                q.push(v);
            }
        }
    }

    std::vector<std::pair<int, int>> search(const std::string& T) {
        std::vector<std::pair<int, int>> result;
        int cur = 0;
        for (int i = 0; i < static_cast<int>(T.size()); ++i) {
            char c = T[i];
            while (cur != 0 && nodes[cur].children.find(c) == nodes[cur].children.end()) {
                cur = nodes[cur].fail;
            }
            auto it = nodes[cur].children.find(c);
            if (it != nodes[cur].children.end()) {
                cur = it->second;
            }
            for (int pid : nodes[cur].out) {
                result.push_back({pid, i});
            }
        }
        return result;
    }
};

int main() {
    AhoCorasick ac;
    ac.add_pattern("he");
    ac.add_pattern("she");
    ac.add_pattern("his");
    ac.add_pattern("hers");
    ac.build_failure();

    std::string T = "ushers";
    std::cout << "T = " << T << '\n';
    std::cout << "Patterns: he, she, his, hers\n";
    std::cout << "Matches:\n";

    auto matches = ac.search(T);
    for (auto& m : matches) {
        int pid = m.first;
        int end = m.second;
        int start = end - static_cast<int>(ac.patterns[pid].size()) + 1;
        std::cout << "  '" << ac.patterns[pid] << "' at [" << start
                  << ".." << end << "]\n";
    }
    return 0;
}

Output yang Dihasilkan:

text 
T = ushers
Patterns: he, she, his, hers
Matches:
  'she' at [1..3]
  'he' at [2..3]
  'hers' at [2..5]
  1. std::vector<ACNode> nodes;: dinamis; node 0 = root. Setiap node menyimpan children map, fail link, dan daftar output.
  2. add_pattern: traverse trie per karakter, buat node bila belum ada. Pada akhir pattern, catat indeks pattern di out.
  3. build_failure BFS: proses level demi level. Anak root langsung dapat fail = 0. Untuk node v anak u via karakter c:
    • Mulai dari f = fail[u] lalu ikuti fail naik hingga menemukan node dengan anak c (atau root).
    • Set fail[v] = anak_c(f) bila ada, atau root.
    • Output inheritance: copy semua output dari fail[v] ke v sehingga saat sampai di v, kita langsung tahu semua pattern yang match (termasuk yang suffix).
  4. search: scan text per karakter. Bila anak c tidak ada, ikuti fail link (mirip KMP). Bila ada, maju ke anak tersebut. Kumpulkan semua output node saat ini — sudah termasuk suffix pattern.
  5. Hasil ushers: tiga pattern match — "she" di [1..3], "he" di [2..3], "hers" di [2..5]. "his" tidak ditemukan.
  6. Kenapa "he" otomatis match? Saat text "she" selesai di node SHE, output inheritance dari fail link (HE) menambahkan pattern "he" ke output SHE. Karena suffix "he" dari "she" memang pattern.

Kompleksitas #

TahapWaktuRuang
Build trie`O(ΣP_i
Build failure (BFS)`O(ΣP_i
SearchO(n + jumlah_match)`O(Σ
Total`O(ΣP_i

Σ|P_i| = total panjang semua pattern. n = panjang text. match = total kemunculan semua pattern di text.

Optimasi: goto Function dengan Array #

Implementasi di atas memakai std::unordered_map per node — overhead besar untuk alphabet kecil. Untuk alphabet ASCII 256, ganti dengan int children[256] (-1 = tidak ada):

cpp 
struct ACNode {
    int children[256];
    int fail = 0;
    std::vector<int> out;
    ACNode() { std::fill(children, children + 256, -1); }
};

Memori O(256 · jumlah_node) — lebih besar per node tetapi akses O(1) tanpa hash lookup. Untuk alphabet besar (Unicode), unordered_map tetap lebih hemat.

Aplikasi Nyata #

  • Virus scanner: database ribuan signature string, scan file binary sekaligus.
  • IDS/IPS jaringan: Snort dan Suricata memakai Aho-Corasick terhadap stream paket TCP.
  • Content filtering: deteksi kata-kata terlarang atau spam pattern di email/chat.
  • DNA motif search: cari ribuan motif sekuens secara paralel.
  • Sensor konten: filter kata sensitif di forum/komentar.

Variasi #

1. Aho-Corasick dengan Output Count Only #

Bila hanya butuh jumlah kemunculan (bukan posisi), tidak perlu push ke vector — cukup inkrementasi counter per pattern. Hemat memori dan waktu.

2. Aho-Corasick dengan Wildcard #

Untuk dukungan pattern seperti "h?s" (? = karakter apa pun), perlu modifikasi failure link karena ? adalah meta character. Implementasi lebih kompleks; biasanya dilakukan dengan meng-expand pattern menjadi semua kemungkinan konkret.

3. Aho-Corasick + Dynamic Pattern #

Standard Aho-Corasick statis (pattern ditentukan sebelum build). Untuk dynamic add/remove pattern, gunakan struktur incremental seperti Aho-Corasick Automaton + balanced BST.

Perbandingan Multi-Pattern #

AlgoritmaBuildSearch (k pattern)Cocok untuk
KMP × kO(k·m)O(k·n)Pattern sedikit
Rabin-Karp + hash setO(k·m)O(n + k) avgPattern sedang, hash konsisten
Aho-Corasick`O(ΣP_i)`
Suffix array (preprocess text)O(n log n)O(k · m log n)Text tetap, banyak query

Ringkasan #

  • Aho-Corasick adalah algoritma multi-pattern matching dengan kompleksitas O(Σ|P_i| + n + match).
  • Dua struktur inti: trie dari semua pattern dan failure link mirip KMP.
  • Failure link via BFS; output inheritance menangkap suffix pattern secara otomatis.
  • Search hanya satu scan text — tidak ada faktor k (jumlah pattern).
  • Aplikasi utama: virus scanner, IDS jaringan, content filter, DNA motif.
  • Optimasi dengan array children[256] untuk alphabet kecil; unordered_map untuk alphabet besar.
  • Untuk pattern sedikit, pertimbangkan Rabin-Karp multi-pattern; Aho-Corasick unggul saat pattern banyak dengan prefix sharing.