Chương trình Python đếm phép toán biến chuỗi thành nối đôi chuỗi con giống nhau

Cho chuỗi chữ thường s. Phép toán: xóa, chèn, hoặc thay thế 1 ký tự. Tìm số phép tối thiểu để s = t + t (nối 2 chuỗi con giống hệt nhau).

Ví dụ

Input: s = "pqrxqsr"

Output: 2

Giải thích: Thay 'x' → 'p', xóa 's' → "pqrpqr" = "pqr" + "pqr".

Thuật toán (Edit Distance + Thử mọi vị trí cắt)

1. Hàm edit_distance(s1, s2) tính khoảng cách Levenshtein (sử dụng DP 1D tiết kiệm không gian).
2. Duyệt mọi vị trí cắt i từ 0 đến len(s):
   • Tính edit_distance(s[:i], s[i:])
   • Cập nhật kết quả nhỏ nhất.

Mã nguồn Python

def solve(s):
    def edit_distance(s1, s2):
        m, n = len(s1), len(s2)
        cur = list(range(n + 1))
        for i in range(m):
            prev, cur = cur, [i + 1] + [0] * n
            for j in range(n):
                if s1[i] == s2[j]:
                    cur[j + 1] = prev[j]
                else:
                    cur[j + 1] = min(cur[j], prev[j], prev[j + 1]) + 1
        return cur[n]

    res = len(s)
    for i in range(len(s) + 1):
        res = min(edit_distance(s[:i], s[i:]), res)
    return res

# Test
s = "pqrxqsr"
print(solve(s))  # Output: 2

Độ phức tạp

• Thời gian: O(n³) — n vị trí cắt × O(n²) edit distance.
• Không gian: O(n) cho mảng DP 1D.

Lưu ý: Có thể tối ưu hóa thêm bằng cách quan sát cấu trúc bài toán, nhưng giải pháp này đủ rõ ràng và đúng.