Cho hai chuỗi, nhiệm vụ in chuỗi con chung dài nhất (Longest Common Substring). Ta giải quyết bằng SequenceMatcher.find_longest_match() trong Python.
Class difflib.SequenceMatcher là class linh hoạt so sánh cặp chuỗi bất kỳ, miễn là phần tử có thể hash.
find_longest_match(a, x, b, y)
Tìm khối khớp dài nhất trong a[a:x] và b[b:y].
Ví dụ
Input: str1 = "pythonprogramming", str2 = "pro" Output: pro
Thuật toán
Bước 1: Nhập hai chuỗi. Bước 2: Khởi tạo đối tượng SequenceMatcher với chuỗi đầu vào. Bước 3: Tìm khớp chuỗi con dài nhất. Bước 4: In chuỗi con chung dài nhất.
Mã ví dụ
# Chương trình Python tìm Chuỗi Con Chung Dài Nhất from difflib import SequenceMatcher def matchsubstring(m,n): seqMatch = SequenceMatcher(None,m,n) match = seqMatch.find_longest_match(0, len(m), 0, len(n)) if (match.size != 0): print ("Chuỗi Con Chung ::>", m[match.a: match.a + match.size]) else: print ('Không tìm thấy chuỗi con chung dài nhất') # Chương trình chính if __name__ == "__main__": X = input("Nhập Chuỗi Thứ Nhất ") Y = input("Nhập Chuỗi Thứ Hai ") matchsubstring(X,Y) Kết quả
Nhập Chuỗi Thứ Nhất pythonprogramming Nhập Chuỗi Thứ Hai pro Chuỗi Con Chung ::> pro