Mô phỏng thuật toán Tìm mọi hoán vị chữ (anagram)

Find All Anagrams · Nhóm: Cửa sổ trượt

Tìm mọi vị trí bắt đầu của hoán vị (anagram) của mẫu p trong chuỗi s, bằng cửa sổ trượt cố định cỡ |p| và so bảng tần suất.

Ý tưởng

Đếm nhu cầu need cho từng ký tự của p; trượt cửa sổ cỡ m = |p| qua s, nạp ký tự vào bên phải và bỏ ký tự rời ra bên trái để giữ cửa sổ luôn cỡ m.

Mỗi khi cửa sổ đủ cỡ m, so bảng tần suất cửa sổ với need; nếu trùng khớp thì cửa sổ đó là một anagram, ghi lại chỉ số bắt đầu.

Vì sao đúng

Cửa sổ cỡ cố định nên mỗi ký tự chỉ vào và ra đúng một lần, phần trượt là O(n); so tần suất trên bảng cố định (26 chữ cái) là O(1) mỗi cửa sổ nên tổng vẫn O(n).

Mã Python

def find_anagrams(s, p):
    m = len(p)
    need = Counter(p)
    win = Counter()
    res = []
    for R, c in enumerate(s):
        win[c] += 1
        if R >= m:
            L = R - m
            win[s[L]] -= 1
            if win[s[L]] == 0: del win[s[L]]
        if win == need:
            res.append(R - m + 1)
    return res

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.