Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> Lập Trình

Giới thiệu Thuật toán Tìm kiếm Mẫu (Introduction to Pattern Searching Algorithms)


Thuật toán tìm kiếm mẫu dùng để tìm mẫu hoặc chuỗi con từ chuỗi lớn hơn. Có nhiều thuật toán khác nhau. Mục tiêu chính là giảm độ phức tạp thời gian. Cách truyền thống có thể tốn nhiều thời gian cho văn bản dài.

Ở đây sẽ thấy các thuật toán để có hiệu năng tốt hơn cho khớp mẫu.

Trong phần này sẽ bao gồm:

  • Thuật toán Aho-Corasick
  • Tìm kiếm mẫu Anagram
  • Heuristic ký tự xấu (Bad Character Heuristic)
  • Thuật toán Boyer-Moore
  • Xây dựng Automation hữu hạn hiệu quả
  • Thuật toán Kasai
  • Thuật toán Knuth-Morris-Pratt (KMP)
  • Thuật toán Manacher
  • Tìm kiếm mẫu Naive
  • Thuật toán Rabin-Karp
  • Mảng hậu tố (Suffix Array)
  • Cây Trie của tất cả hậu tố
  • Thuật toán Z