Aho Corasick
Nguồn: emaxx
Lưu ý¶
Trước khi đọc bài viết này bạn cần nắm được các kiến thức sau:
Giới thiệu¶
Như các bạn đã biết:
- Thuật toán KMP giúp tìm kiếm 1 xâu con (pattern) trong 1 xâu lớn với độ phức tạp \(O(M + N)\) với \(M\) và \(N\) là độ dài 2 xâu.
- Cấu trúc dữ liệu Trie giúp chúng ta lưu trữ và tìm kiếm \(N\).
Cấu trúc dữ liệu Aho-Corasick có thể hình dung như 1 sự kết hợp giữa trie và KMP:
// IN PROGRESS