Tìm kiếm mẫu Anagram (Anagram Pattern Search)

Anagram là các hoán vị của một chuỗi/pattern cho trước. Thuật toán này không chỉ tìm pattern chính xác mà tìm tất cả các sắp xếp có thể của pattern trong text.

Chia text thành các cửa sổ (window) độ dài bằng pattern. Đếm tần suất ký tự của pattern lưu vào mảng. Với mỗi window, đếm tần suất và so sánh.

Độ phức tạp: O(n)

Input và Output

Input: Main String: "AABAACBABBCABAABBA", Pattern: "AABC"
Output: Anagram found at position: 2
Anagram found at position: 3
Anagram found at position: 4
Anagram found at position: 10

Thuật toán

anagramSearch(text, pattern)
Input: Chuỗi chính, pattern
Output: Vị trí pattern và anagram tìm thấy

Begin
  định nghĩa patternFreq[], stringFreq[]
  patLen := pattern length, strLen := text length
  khởi tạo patternFreq = 0
  for chars in pattern do tăng freq done
  for i := 0 to strLen - patLen do
    khởi tạo stringFreq = 0
    for chars in window i..i+patLen-1 do tăng freq done
    if stringFreq == patternFreq thì in i (tìm thấy anagram)
  done
End

Ví dụ (C++)

#include <iostream>
#include <cstring>
#define LETTER 26
using namespace std;

bool arrayCompare(int *a1, int *a2, int n) {
    for(int i=0;i
Kết quả
Anagram found at position: 2
Anagram found at position: 3
Anagram found at position: 4
Anagram found at position: 10
Tối ưu: Dùng sliding window cập nhật tần suất O(1) thay vì đếm lại toàn bộ window: trừ ký tự ra khỏi window, thêm ký tự vào window. Giảm độ phức tạp hằng số.