Chương trình Python Anagram Substring Search (Tìm anagram con)

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ụ

MAX = 300

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

def search(pat, txt):
    M = len(pat)
    N = len(txt)
    countP = [0] * MAX
    countTW = [0] * MAX
    for i in range(M):
        countP[ord(pat[i])] += 1
        countTW[ord(txt[i])] += 1
    for i in range(M, N):
        if compare(countP, countTW):
            print("Tìm thấy tại index", (i-M))
        countTW[ord(txt[i])] += 1
        countTW[ord(txt[i-M])] -= 1
    if compare(countP, countTW):
        print("Tìm thấy tại index:", N-M)

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.