Chương trình Python xoay mảng (array rotation)

Trong bài viết này, chúng ta sẽ tìm hiểu giải pháp cho bài toán sau:

Đề bài – Cho văn bản và mẫu, cần in tất cả vị trí xuất hiện của mẫu và các hoán vị (anagram) của nó trong văn bản.

Hãy quan sát giải pháp trong triển khai dưới đây:

Ví dụ

# giá trị tối đa
MAX = 300

# so sánh
def compare(arr1, arr2):
    for i in range(MAX):
        if arr1[i] != arr2[i]:
            return False
    return True

# tìm kiếm
def search(pat, txt):
    M = len(pat)
    N = len(txt)
    # countP: đếm pattern, countTW: đếm cửa sổ text
    countP = [0] * MAX
    countTW = [0] * MAX
    for i in range(M):
        countP[ord(pat[i])] += 1
        countTW[ord(txt[i])] += 1
    # duyệt
    for i in range(M, N):
        # so sánh cửa sổ hiện tại và pattern
        if compare(countP, countTW):
            print("Tìm thấy tại index", (i-M))
        # thêm ký tự vào cửa sổ
        countTW[ord(txt[i])] += 1
        # xóa ký tự khỏi cửa sổ
        countTW[ord(txt[i-M])] -= 1
    # kiểm tra cửa sổ cuối
    if compare(countP, countTW):
        print("Tìm thấy tại index:", N-M)

# main
txt = "TUTORIALSPOINT"
pat = "TOR"
search(pat, txt)

Kết quả

Tìm thấy tại index 2

Kết luận

Trong bài này, chúng ta đã học cách làm chương trình Python Anagram Substring Search.