Tìm kiếm chuỗi con anagram bằng Python

Trong hướng dẫn này, chúng ta sẽ viết chương trình tìm tất cả các anagram (chữ đảo) của một chuỗi cho trước trong một chuỗi lớn hơn.

Ví dụ minh họa

Input: anagram = "cat", string = "tacghactcat"
Output: Anagram at 0, Anagram at 5, Anagram at 7, Anagram at 8

Thuật toán

1. Khởi tạo hai chuỗi: chuỗi mẫu (anagram) và chuỗi cần tìm kiếm.
2. Tạo hàm kiểm tra xem hai chuỗi có phải là anagram của nhau không (so sánh tần suất ký tự).
3. Duyệt qua chuỗi chính, lấy từng chuỗi con có độ dài bằng chuỗi mẫu.
4. Gọi hàm kiểm tra anagram cho mỗi chuỗi con.
5. Nếu là anagram, in ra chỉ số bắt đầu của chuỗi con đó.

Mã nguồn Python

# importing collections to check for anagrams
import collections

# initializing two strings
anagram = 'cat'
string = 'tacghactcat'

# function to check for anagrams
def is_anagram(substr):
    # checking for anagram using Counter
    if collections.Counter(anagram) == collections.Counter(substr):
        return True
    else:
        return False

# getting lengths of both strings
anagram_len = len(anagram)
string_len = len(string)

# iterating through the string
for i in range(string_len - anagram_len + 1):
    # checking for anagram
    if is_anagram(string[i:i+anagram_len]):
        # printing the index
        print(f'Anagram at {i}')

Kết quả

Anagram at 0
Anagram at 5
Anagram at 7
Anagram at 8

Kết luận

Chương trình sử dụng collections.Counter để so sánh tần suất ký tự một cách hiệu quả. Nếu bạn có thắc mắc, hãy để lại bình luận.