Aho-Corasick — Multi-Pattern Matching

Hệ thống Intrusion Detection Snort quét mỗi network packet so với hơn 30.000 attack signature trong real-time — dưới 1μs per packet. ClamAV antivirus scan file so với database hơn 6 triệu malware signature. Nếu dùng KMP riêng cho từng signature, 30.000 pattern × O(n) = O(30.000n) per packet — hoàn toàn không khả thi. Cả hai hệ thống đều dùng Aho-Corasick, thuật toán cho phép matching tất cả pattern trong một lần duyệt text duy nhất.

Aho-Corasick, công bố năm 1975 bởi Alfred Aho và Margaret Corasick, kết hợp hai ý tưởng bạn đã biết: Trie (lưu trữ tất cả patterns) và failure function từ KMP (tránh backtrack khi mismatch). Kết quả là một Deterministic Finite Automaton hoàn chỉnh xử lý mỗi ký tự input đúng một lần, đạt O(n + m + z) — n là text length, m là tổng pattern lengths, z là số match tìm được.

Nắm vững Aho-Corasick là bước cuối cùng trong bộ công cụ string processing. Nếu KMP là "một viên đạn tìm một mục tiêu", Aho-Corasick là "radar quét toàn bộ vùng trời" — chạm vào mọi target cùng lúc mà chi phí gần như không đổi.

Bức tranh tư duy

Hình dung hệ thống kiểm tra an ninh sân bay. Mỗi hành khách (ký tự trong text) đi qua một hành lang duy nhất. Dọc hành lang có nhiều "trạm kiểm tra" (nodes trong Trie), mỗi trạm nhận diện một phần của vật phẩm nguy hiểm (pattern).

Khi hành khách khớp với một trạm, họ tiến sang trạm tiếp theo. Nếu không khớp, thay vì quay lại từ đầu, hệ thống có đường tắt (failure link) đưa về trạm phù hợp nhất — nơi mà phần đã khớp trùng với suffix. Và khi một pattern hoàn chỉnh được phát hiện, output link báo ngay: "tìm thấy vật phẩm X, cả vật phẩm Y nữa!" (vì Y là suffix của X).

AUTOMATON CHO PATTERNS: {"he", "she", "his", "hers"}

Trie structure + Failure links (--->) + Output:

         (root)
        /      \
       h        s
       |        |
      (h)      (s)
      / \       |
     e   i     h
     |   |     |
   *(he) (hi) (sh)──────> (h)     ← failure: "h" là suffix của "sh"
     |    |     |
     r    s    e
     |    |    |
   (her) *(his) *(she)───> *(he)  ← failure: "he" là suffix của "she"
     |                              output: {"she", "he"}
     s
     |
   *(hers)

  * = output node (pattern found)
  ──> = failure link

Xử lý text "ushers":
  u: root→root (no 'u' child) 
  s: root→(s)
  h: (s)→(sh)
  e: (sh)→*(she)  → OUTPUT: "she" tại vị trí 3
                   → follow output: "he" tại vị trí 3
  r: *(she)→fail→*(he)→(her)
  s: (her)→*(hers) → OUTPUT: "hers" tại vị trí 5

📌 Khi nào analogy bị phá vỡ

Sân bay chỉ tìm 1 vật phẩm nguy hiểm rồi dừng. Aho-Corasick tìm tất cả occurrences — bao gồm overlapping. Text "ushers" chứa đồng thời "she", "he", và "hers".

Cốt lõi kỹ thuật

Ba giai đoạn xây dựng

Aho-Corasick automaton được xây dựng qua 3 bước:

1. Build Trie — insert tất cả patterns vào Trie chuẩn
2. Build Failure Links — BFS từ root, tính failure cho mỗi node
3. Build Output Links — merge output của node hiện tại với output của failure chain

Giai đoạn 1: Build Trie

Giống hệt Trie chuẩn. Insert từng pattern, đánh dấu end-of-word.

Giai đoạn 2: Failure Links (BFS)

Failure link của node v trỏ đến node sâu nhất trong Trie mà label path là proper suffix của label path đến v.

Quy tắc:
1. Children trực tiếp của root → failure = root
2. Cho node v với parent u, ký tự c:
   - Bắt đầu từ failure(u)
   - Nếu failure(u) có child c → failure(v) = failure(u).child[c]
   - Nếu không → tiếp tục failure(failure(u))
   - Nếu về root mà vẫn không có child c → failure(v) = root

Giai đoạn 3: Output Links

Mỗi node lưu tập hợp tất cả patterns kết thúc tại hoặc "ẩn sau" node đó:

output(v) = (patterns kết thúc tại v) ∪ output(failure(v))

Ví dụ: node *(she) có output = {"she"} ∪ output(failure("she")) = {"she"} ∪ {"he"} = {"she", "he"}.

Implementation hoàn chỉnh

C++

#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <string>

struct ACNode {
    std::unordered_map<char, int> children; // char → node index
    int failure = 0;
    std::vector<std::string> output;
};

class AhoCorasick {
    std::vector<ACNode> nodes;

public:
    AhoCorasick() { nodes.emplace_back(); } // root = index 0

    void addPattern(const std::string& pattern) {
        int cur = 0;
        for (char c : pattern) {
            if (!nodes[cur].children.count(c)) {
                nodes[cur].children[c] = nodes.size();
                nodes.emplace_back();
            }
            cur = nodes[cur].children[c];
        }
        nodes[cur].output.push_back(pattern);
    }

    void build() {
        std::queue<int> q;
        // Depth 1: failure = root
        for (auto& [c, child] : nodes[0].children) {
            nodes[child].failure = 0;
            q.push(child);
        }

        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (auto& [c, v] : nodes[u].children) {
                q.push(v);
                int f = nodes[u].failure;
                while (f && !nodes[f].children.count(c))
                    f = nodes[f].failure;
                nodes[v].failure =
                    nodes[f].children.count(c) && nodes[f].children[c] != v
                    ? nodes[f].children[c] : 0;
                // Merge output
                auto& fo = nodes[nodes[v].failure].output;
                nodes[v].output.insert(
                    nodes[v].output.end(), fo.begin(), fo.end());
            }
        }
    }

    std::vector<std::pair<int, std::string>> search(const std::string& text) {
        std::vector<std::pair<int, std::string>> results;
        int cur = 0;
        for (int i = 0; i < (int)text.size(); i++) {
            char c = text[i];
            while (cur && !nodes[cur].children.count(c))
                cur = nodes[cur].failure;
            if (nodes[cur].children.count(c))
                cur = nodes[cur].children[c];
            for (auto& pat : nodes[cur].output)
                results.emplace_back(i - (int)pat.size() + 1, pat);
        }
        return results;
    }
};

Python

from typing import List, Dict, Tuple, Optional
from collections import deque

class AhoCorasick:
    def __init__(self) -> None:
        self.children: List[Dict[str, int]] = [{}]  # node 0 = root
        self.failure: List[int] = [0]
        self.output: List[List[str]] = [[]]
        self._built = False

    def add_pattern(self, pattern: str) -> None:
        if not pattern:
            return
        self._built = False
        cur = 0
        for ch in pattern:
            if ch not in self.children[cur]:
                self.children[cur][ch] = len(self.children)
                self.children.append({})
                self.failure.append(0)
                self.output.append([])
            cur = self.children[cur][ch]
        self.output[cur].append(pattern)

    def build(self) -> None:
        """Xây failure links bằng BFS từ root."""
        queue = deque()
        # Depth 1: failure → root
        for ch, child in self.children[0].items():
            self.failure[child] = 0
            queue.append(child)

        while queue:
            u = queue.popleft()
            for ch, v in self.children[u].items():
                queue.append(v)
                f = self.failure[u]
                while f and ch not in self.children[f]:
                    f = self.failure[f]
                self.failure[v] = (
                    self.children[f][ch]
                    if ch in self.children[f]
                       and self.children[f][ch] != v
                    else 0
                )
                # Merge output từ failure chain
                self.output[v] = (
                    self.output[v] + self.output[self.failure[v]]
                )
        self._built = True

    def search(self, text: str) -> List[Tuple[int, str]]:
        """Tìm tất cả pattern occurrences trong text."""
        if not self._built:
            self.build()

        results: List[Tuple[int, str]] = []
        cur = 0

        for i, ch in enumerate(text):
            while cur and ch not in self.children[cur]:
                cur = self.failure[cur]
            if ch in self.children[cur]:
                cur = self.children[cur][ch]
            for pat in self.output[cur]:
                results.append((i - len(pat) + 1, pat))

        return results

    def contains_any(self, text: str) -> bool:
        """Kiểm tra nhanh text có chứa bất kỳ pattern nào."""
        if not self._built:
            self.build()
        cur = 0
        for ch in text:
            while cur and ch not in self.children[cur]:
                cur = self.failure[cur]
            if ch in self.children[cur]:
                cur = self.children[cur][ch]
            if self.output[cur]:
                return True
        return False

Java

import java.util.*;

public class AhoCorasick {
    private List<Map<Character, Integer>> children = new ArrayList<>();
    private List<Integer> failure = new ArrayList<>();
    private List<List<String>> output = new ArrayList<>();
    private boolean built = false;

    public AhoCorasick() {
        children.add(new HashMap<>());
        failure.add(0);
        output.add(new ArrayList<>());
    }

    public void addPattern(String pattern) {
        built = false;
        int cur = 0;
        for (char c : pattern.toCharArray()) {
            if (!children.get(cur).containsKey(c)) {
                children.get(cur).put(c, children.size());
                children.add(new HashMap<>());
                failure.add(0);
                output.add(new ArrayList<>());
            }
            cur = children.get(cur).get(c);
        }
        output.get(cur).add(pattern);
    }

    public void build() {
        Queue<Integer> queue = new LinkedList<>();
        for (var entry : children.get(0).entrySet()) {
            failure.set(entry.getValue(), 0);
            queue.add(entry.getValue());
        }

        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (var entry : children.get(u).entrySet()) {
                char c = entry.getKey();
                int v = entry.getValue();
                queue.add(v);
                int f = failure.get(u);
                while (f != 0 && !children.get(f).containsKey(c))
                    f = failure.get(f);
                int fv = children.get(f).getOrDefault(c, 0);
                failure.set(v, fv != v ? fv : 0);
                List<String> merged = new ArrayList<>(output.get(v));
                merged.addAll(output.get(failure.get(v)));
                output.set(v, merged);
            }
        }
        built = true;
    }

    public List<int[]> search(String text) {
        if (!built) build();
        List<int[]> results = new ArrayList<>();
        int cur = 0;
        for (int i = 0; i < text.length(); i++) {
            char c = text.charAt(i);
            while (cur != 0 && !children.get(cur).containsKey(c))
                cur = failure.get(cur);
            if (children.get(cur).containsKey(c))
                cur = children.get(cur).get(c);
            for (String pat : output.get(cur))
                results.add(new int[]{i - pat.length() + 1, pat.length()});
        }
        return results;
    }
}

Go

type AhoCorasick struct {
    children []map[byte]int
    failure  []int
    output   [][]string
    built    bool
}

func NewAhoCorasick() *AhoCorasick {
    return &AhoCorasick{
        children: []map[byte]int{{}},
        failure:  []int{0},
        output:   [][]string{{}},
    }
}

func (ac *AhoCorasick) AddPattern(pattern string) {
    ac.built = false
    cur := 0
    for i := 0; i < len(pattern); i++ {
        c := pattern[i]
        if _, ok := ac.children[cur][c]; !ok {
            ac.children[cur][c] = len(ac.children)
            ac.children = append(ac.children, map[byte]int{})
            ac.failure = append(ac.failure, 0)
            ac.output = append(ac.output, nil)
        }
        cur = ac.children[cur][c]
    }
    ac.output[cur] = append(ac.output[cur], pattern)
}

func (ac *AhoCorasick) Build() {
    queue := []int{}
    for _, child := range ac.children[0] {
        ac.failure[child] = 0
        queue = append(queue, child)
    }

    for len(queue) > 0 {
        u := queue[0]
        queue = queue[1:]
        for c, v := range ac.children[u] {
            queue = append(queue, v)
            f := ac.failure[u]
            for f != 0 {
                if _, ok := ac.children[f][c]; ok {
                    break
                }
                f = ac.failure[f]
            }
            if fv, ok := ac.children[f][c]; ok && fv != v {
                ac.failure[v] = fv
            } else {
                ac.failure[v] = 0
            }
            ac.output[v] = append(
                append([]string{}, ac.output[v]...),
                ac.output[ac.failure[v]]...,
            )
        }
    }
    ac.built = true
}

type Match struct {
    Position int
    Pattern  string
}

func (ac *AhoCorasick) Search(text string) []Match {
    if !ac.built {
        ac.Build()
    }
    var results []Match
    cur := 0
    for i := 0; i < len(text); i++ {
        c := text[i]
        for cur != 0 {
            if _, ok := ac.children[cur][c]; ok {
                break
            }
            cur = ac.failure[cur]
        }
        if next, ok := ac.children[cur][c]; ok {
            cur = next
        }
        for _, pat := range ac.output[cur] {
            results = append(results, Match{i - len(pat) + 1, pat})
        }
    }
    return results
}

Thực chiến

Tình huống: Content Filtering Service

Bối cảnh: Chat platform phục vụ 5 triệu người dùng. Cần filter 8.000 từ cấm (hate speech, spam URLs, sensitive keywords) trong real-time. Mỗi tin nhắn trung bình 200 ký tự, throughput 50.000 messages/giây.

Mục tiêu: Latency < 0.1ms per message, false negative = 0 (không bỏ sót).

Python

from typing import List, Tuple, Optional
from dataclasses import dataclass

@dataclass
class FilterResult:
    is_clean: bool
    violations: List[Tuple[int, str]]  # (position, matched_word)

class ContentFilter:
    """Production content filter dùng Aho-Corasick."""

    def __init__(self, banned_words: List[str]) -> None:
        self.ac = AhoCorasick()
        for word in banned_words:
            normalized = word.lower().strip()
            if normalized:
                self.ac.add_pattern(normalized)
        self.ac.build()

    def check(self, message: str) -> FilterResult:
        """Kiểm tra message, trả về danh sách vi phạm."""
        normalized = message.lower()
        matches = self.ac.search(normalized)
        return FilterResult(
            is_clean=len(matches) == 0,
            violations=matches,
        )

    def censor(self, message: str, mask: str = "***") -> str:
        """Thay thế từ cấm bằng mask."""
        result = list(message)
        normalized = message.lower()
        matches = self.ac.search(normalized)

        for pos, pattern in matches:
            for i in range(pos, pos + len(pattern)):
                if i < len(result):
                    result[i] = '*'

        return ''.join(result)

C++

#include <string>
#include <vector>
#include <algorithm>

struct FilterResult {
    bool isClean;
    std::vector<std::pair<int, std::string>> violations;
};

class ContentFilter {
    AhoCorasick ac;

public:
    ContentFilter(const std::vector<std::string>& bannedWords) {
        for (auto& w : bannedWords) {
            std::string norm = w;
            std::transform(norm.begin(), norm.end(), norm.begin(), ::tolower);
            if (!norm.empty()) ac.addPattern(norm);
        }
        ac.build();
    }

    FilterResult check(const std::string& message) {
        std::string norm = message;
        std::transform(norm.begin(), norm.end(), norm.begin(), ::tolower);
        auto matches = ac.search(norm);
        return {matches.empty(), matches};
    }

    std::string censor(const std::string& message) {
        std::string result = message;
        std::string norm = message;
        std::transform(norm.begin(), norm.end(), norm.begin(), ::tolower);
        auto matches = ac.search(norm);
        for (auto& [pos, pat] : matches)
            for (int i = pos; i < pos + (int)pat.size() && i < (int)result.size(); i++)
                result[i] = '*';
        return result;
    }
};

Phân tích:

• 8.000 patterns: Build automaton một lần (O(m) ≈ O(80.000 ký tự) ≈ 1ms). Search mỗi message O(200) ≈ microseconds
• vs. KMP riêng lẻ: 8.000 × KMP = O(8.000 × 200) = 1.6M comparisons/message. Aho-Corasick: O(200) — nhanh hơn 8.000 lần
• Normalize: Lowercase cả patterns lẫn input để tránh bypass bằng case variation

Tình huống: Network IDS Signature Matching

Bối cảnh: Snort-like IDS quét 10Gbps network traffic, match 30.000 attack signatures.

class NetworkIDS:
    """Simplified IDS signature matcher."""

    def __init__(self, signatures: List[str]) -> None:
        self.ac = AhoCorasick()
        for sig in signatures:
            self.ac.add_pattern(sig)
        self.ac.build()

    def scan_packet(self, payload: bytes) -> List[Tuple[int, str]]:
        """Quét packet payload, trả về matched signatures."""
        text = payload.decode('latin-1', errors='replace')
        return self.ac.search(text)

Sai lầm điển hình

❌ Sai lầm 1: Quên gọi build() sau khi add patterns

Vấn đề: Search trên Trie chưa có failure links.

# SAI: search không có failure links
ac = AhoCorasick()
for w in words:
    ac.add_pattern(w)
# QUÊN: ac.build()
result = ac.search(text)  # failure links = 0 → miss matches!

Tại sao sai: Không có failure links, automaton không fallback khi mismatch → bỏ sót pattern mà suffix trùng với prefix pattern khác. Ví dụ: "she" sẽ không trigger output "he" nếu failure link thiếu.

# ĐÚNG: luôn build trước search
ac = AhoCorasick()
for w in words:
    ac.add_pattern(w)
ac.build()  # BẮT BUỘC
result = ac.search(text)

❌ Sai lầm 2: Dùng Aho-Corasick cho 1 pattern

Vấn đề: Overhead xây automaton cho single pattern.

# SAI: 1 pattern mà dùng Aho-Corasick?
ac = AhoCorasick()
ac.add_pattern("error")
ac.build()
ac.search(log_text)

Tại sao sai: Aho-Corasick build O(m × Σ) trong practice, dùng dict per node. Cho 1 pattern, KMP nhanh hơn và dùng ít memory hơn (chỉ 1 array LPS).

# ĐÚNG: KMP cho single pattern
from kmp import kmp_search
result = kmp_search(log_text, "error")

# Aho-Corasick khi ≥ 10 patterns

❌ Sai lầm 3: Case mismatch giữa patterns và text

Vấn đề: Pattern lowercase nhưng text uppercase → bỏ sót.

# SAI: không normalize
ac.add_pattern("malware")
ac.search("MALWARE detected")  # miss!

Tại sao sai: Aho-Corasick so sánh exact character. 'M' ≠ 'm' trong ASCII.

# ĐÚNG: normalize cả patterns lẫn text
ac.add_pattern(word.lower())
ac.search(text.lower())

Under the Hood

Phân tích thời gian chi tiết

Phase	Time	Space
Build Trie	O(m)	O(m × Σ) worst
Build Failure Links	O(m)	Reuse Trie nodes
Build Output Links	O(m)	O(m) merged
Search	O(n + z)	O(1) auxiliary
Tổng	O(n + m + z)	O(m × Σ)

Với: n = text length, m = tổng pattern lengths, z = số matches, Σ = alphabet size.

Tại sao search là O(n + z), không phải O(n)?

Mỗi ký tự text:
  1. Follow transitions (bao gồm failure links): amortized O(1)
     Chứng minh: giống KMP — failure link giảm depth,
     tổng depth tăng ≤ n, tổng depth giảm ≤ n → O(2n) = O(n)

  2. Report matches: O(|output|) per position
     Tổng qua tất cả positions = z (tổng matches)

→ O(n) cho transitions + O(z) cho reporting = O(n + z)

Automaton state diagram hoàn chỉnh

Patterns: {"ab", "bc", "abc"}

States: 0(root), 1(a), 2(ab*), 3(abc*), 4(b), 5(bc*)

Goto transitions (solid):
  0 --a--> 1
  0 --b--> 4
  1 --b--> 2*
  2 --c--> 3*
  4 --c--> 5*

Failure links (dashed):
  1 --> 0     ("a" → no proper suffix in trie)
  2 --> 4     ("ab" → suffix "b" = state 4)
  3 --> 5     ("abc" → suffix "bc" = state 5*)
  4 --> 0     ("b" → no proper suffix in trie)
  5 --> 0     ("bc" → no proper suffix in trie)

Output:
  state 2: {"ab"}
  state 3: {"abc"} ∪ output(failure(3)) = {"abc", "bc"}
  state 5: {"bc"}

Processing "abcbc":
  a: 0→1          output: {}
  b: 1→2*         output: {"ab"}        ← found "ab" at 0
  c: 2→3*         output: {"abc","bc"}  ← found "abc" at 0, "bc" at 1
  b: 3→fail→5→fail→0→4  output: {}
  c: 4→5*         output: {"bc"}        ← found "bc" at 3

So sánh memory và performance

Tiêu chí	Aho-Corasick	k × KMP	k × Rabin-Karp
Build time	O(m)	O(m)	O(m)
Search time	O(n + z)	O(k × n)	O(k × n) avg
Memory	O(m × Σ)	O(m)	O(k)
k = 10	≈ O(n)	≈ O(10n)	≈ O(10n)
k = 30.000	≈ O(n)	≈ O(30.000n) ❌	≈ O(30.000n) ❌

Trade-offs

Quyết định	Aho-Corasick chọn	Đánh đổi
Pre-built automaton	O(n+z) search	Build time O(m), memory O(m×Σ)
Single pass	Process mỗi char 1 lần	Complex implementation
Eager output merge	O(1) per output at runtime	Duplicate storage in output lists
Dict-based children	Flexible alphabet	Slower than array-based cho fixed Σ

Checklist ghi nhớ

✅ Checklist triển khai

Xây dựng automaton

• [ ] Bước 1: Build Trie — insert tất cả patterns
• [ ] Bước 2: Build failure links bằng BFS (depth 1 → root, rest → traverse failure chain)
• [ ] Bước 3: Merge output — output(v) = local(v) ∪ output(failure(v))
• [ ] Gọi build() SAU KHI add hết patterns, TRƯỚC KHI search

Failure links

• [ ] Children trực tiếp của root luôn có failure = root
• [ ] Failure(v) = node sâu nhất mà path là proper suffix của path(v)
• [ ] BFS đảm bảo parent failure đã tính trước khi tính children

Search

• [ ] Mỗi ký tự: follow children hoặc failure links cho đến match hoặc root
• [ ] Tại mỗi state, report TẤT CẢ patterns trong output (bao gồm failure chain)
• [ ] Overlapping matches được tìm tự động nhờ output merging

Production

• [ ] Normalize patterns và text (lowercase, trim) trước khi xử lý
• [ ] Build automaton 1 lần, search nhiều lần — amortize build cost
• [ ] ≥ 10 patterns: Aho-Corasick. 1 pattern: KMP. 2-9 patterns: đo benchmark
• [ ] Kiểm tra memory footprint — 30.000 patterns × 50 chars ≈ 1.5M nodes

Bài tập luyện tập

Bài 1: Trace automaton bằng tay — Foundation

Đề bài: Cho patterns {"he", "she", "his", "hers"}. Xây dựng Trie, tính failure links, và trace text "ahishers". Liệt kê tất cả matches.

🧠 Quiz

Câu hỏi kiểm tra: Text "ahishers" chứa bao nhiêu pattern matches (bao gồm overlapping)?

• [ ] A. 3
• [ ] B. 4
• [x] C. 5
• [ ] D. 6 Giải thích: "ahishers" chứa: "his" tại 1, "she" tại 3, "he" tại 4 (suffix output), "hers" tại 4, "he" — tổng 5 matches. Lưu ý "he" xuất hiện 2 cách: trực tiếp và qua output link của "she".

💡 Gợi ý

• Build Trie: root → h(e*, r(s*)), h(i(s*)), s(h(e*))
• Failure: she → he, sh → h
• Trace từng ký tự, theo failure links khi mismatch
• Output link: state "she" reports cả "she" và "he"

✅ Lời giải

ac = AhoCorasick()
for p in ["he", "she", "his", "hers"]:
    ac.add_pattern(p)
ac.build()

results = ac.search("ahishers")
print(results)
# Output: [(1, 'his'), (3, 'she'), (3, 'he'), (4, 'hers'), (4, 'he')]
# Hoặc tương tự, tùy thứ tự output merge

Phân tích: 8 ký tự text, 4 patterns tổng 11 chars, 5 matches. Time = O(8 + 11 + 5) = O(24).

Bài 2: Content Filter — Intermediate

Đề bài: Implement hàm censor(text, banned_words) thay thế tất cả từ cấm bằng ***. Test với text "She said his hers are here" và banned = ["he", "she", "his", "hers"].

✅ Lời giải

def censor(text: str, banned_words: List[str]) -> str:
    ac = AhoCorasick()
    for w in banned_words:
        ac.add_pattern(w.lower())
    ac.build()

    result = list(text)
    matches = ac.search(text.lower())

    for pos, pattern in matches:
        for i in range(pos, pos + len(pattern)):
            result[i] = '*'

    return ''.join(result)

print(censor("She said his hers are here", ["he", "she", "his", "hers"]))
# "*** said *** **** are **re"

Phân tích: Overlapping censorship — "hers" censor cả "he" bên trong. Cẩn thận: "here" chỉ bị censor "he" phần đầu, phần "re" giữ nguyên.

Liên kết học tiếp

📚 Bài liên quan

Bài liên quan trong Penalgo

• ← Trie — cấu trúc dữ liệu nền tảng cho Aho-Corasick
• KMP — failure function, nguồn gốc tư duy failure links
• Rabin-Karp — hash-based alternative cho multi-pattern
• String Processing — Tổng quan — so sánh tổng hợp thuật toán

Từ khóa glossary: Aho-Corasick, multi-pattern matching, automaton, failure links, output links, suffix links, IDS, content filtering

Tìm kiếm liên quan: thuật toán đa mẫu, tìm nhiều chuỗi đồng thời, lọc nội dung, phát hiện xâm nhập mạng, quét virus