โปรแกรม Python สำหรับ Anagram Substring Search (การค้นหาย่อหน้า Anagram)

ในบทความนี้ เราจะเรียนรู้วิธีการแก้ปัญหาต่อไปนี้:

ข้อความปัญหา — กำหนดข้อความ (text) และรูปแบบ (pattern) ให้พิมพ์ตำแหน่งทั้งหมดของ pattern และการเรียงสับเปลี่ยนของมัน (anagrams) ใน text

มาเปลี่ยนดูโค้ดตัวอย่างด้านล่างนี้:

ตัวอย่างโค้ด

# ค่าสูงสุด
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 = นับ pattern, countTW = นับ text window
    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):
        # เปรียบเทียบ window ปัจจุบันกับ pattern
        if compare(countP, countTW):
            print("Found at Index", (i - M))
        # เพิ่มตัวอักษรเข้า window
        countTW[ord(txt[i])] += 1
        # ลบตัวอักษรออกจาก window
        countTW[ord(txt[i - M])] -= 1
    # ตรวจสอบ window สุดท้าย
    if compare(countP, countTW):
        print("It is Found at Index :", N - M)

# โปรแกรมหลัก
txt = "TUTORIALSPOINT"
pat = "TOR"
search(pat, txt)

ผลลัพธ์

Found at Index 2

ตัวแปรทั้งหมดถูกประกาศในขอบเขตท้องถิ่น (local scope) และการอ้างอิงของมันแสดงในรูปภาพด้านบน

สรุป

ในบทความนี้ เราได้เรียนรู้วิธีการเขียนโปรแกรม Python สำหรับ Anagram Substring Search