So sánh chuỗi bằng quy hoạch động

Lan muốn đối chiếu hai bản ghi BANANA và ATANA. Các ký tự có thể bị bỏ sót khi chép lại, nhưng thứ tự những ký tự còn lại được giữ nguyên. Lan cần biết hai bản có thể cùng giữ lại bao nhiêu ký tự. Sau đó, bạn ấy muốn tính số lần sửa ít nhất để biến bản thứ nhất thành bản thứ hai.

Độ dài tiền tố giúp dành chỗ cho chuỗi rỗng

Một tiền tố (prefix) gồm các ký tự đầu tiên của chuỗi. Với s = "BAN", s[:2] là "BA"; ký tự cuối tiền tố này là s[1]. Tiền tố độ dài 0 là chuỗi rỗng. Trong bảng, hàng i biểu diễn s[:i], còn cột j biểu diễn t[:j].

Đoạn sau in các tiền tố của "BAN", kể cả tiền tố rỗng:

s = "BAN"
for i in range(len(s) + 1):
    print(i, repr(s[:i]))

0 ''
1 'B'
2 'BA'
3 'BAN'

Khi i > 0, ký tự mới đưa vào là s[i - 1]. Không lấy s[i]: ở i = len(s), chỉ số đó vượt phạm vi. Trạng thái hàng 0 vẫn cần thiết, dù không có ký tự cuối để so sánh.

Dãy con giữ thứ tự nhưng được phép bỏ ký tự

Một dãy con (subsequence) nhận được khi xóa không hoặc nhiều ký tự mà không đổi thứ tự các ký tự còn lại. Dãy "BNA" là dãy con của "BANANA": chọn vị trí 0, 2 và 3. Một chuỗi con (substring) phải gồm các ký tự liên tiếp. Vì thế "BNA" không phải chuỗi con của "BANANA".

Đoạn dưới kiểm tra một dãy con bằng cách quét từ trái sang phải:

def is_subsequence(candidate, text):
    i = 0
    for char in text:
        if i < len(candidate) and candidate[i] == char:
            i += 1
    return i == len(candidate)

print(is_subsequence("BNA", "BANANA"))
print("BNA" in "BANANA")
print(is_subsequence("ANB", "BANANA"))

True
False
False

Phép in với chuỗi kiểm tra đoạn liên tiếp; hàm trên cho phép bỏ ký tự. Chuỗi rỗng là dãy con của mọi chuỗi. Hai khái niệm này dẫn đến hai bảng quy hoạch động khác nhau.

Bảng LCS ghi độ dài tốt nhất của hai tiền tố

Dãy con chung dài nhất (longest common subsequence, LCS) có độ dài lớn nhất trong các dãy con xuất hiện theo thứ tự ở cả hai chuỗi. Đặt dp[i][j] là độ dài LCS của s[:i] và t[:j]. Nếu một tiền tố rỗng, giá trị bằng 0.

Nếu s[i - 1] == t[j - 1], ta nối ký tự chung vào một LCS của hai tiền tố ngắn hơn. Một LCS tối ưu cũng có thể kết thúc bằng ký tự chung này: nếu chưa dùng nó, ta thêm hoặc thay ký tự cuối tương ứng mà không giảm độ dài. Do đó dp[i][j] = dp[i - 1][j - 1] + 1.

Nếu hai ký tự cuối khác nhau, một dãy con chung không thể dùng cả hai làm ký tự cuối. Bỏ một trong hai ký tự là đủ xét mọi khả năng. Ta lấy max(dp[i - 1][j], dp[i][j - 1]).

Bảng sau được chính chương trình tính cho s = "ABCA" và t = "ACBA":

Tại hàng AB, cột AC, hai ký tự cuối khác nhau. Ô phía trên và bên trái đều có giá trị 1, nên ô hiện tại bằng 1. Tại hàng ABC, cột AC, hai ký tự cuối đều là C, nên lấy ô chéo cộng một. Hai nhánh đều xuất hiện trong cùng một bảng.

Chương trình sau đọc đúng hai dòng; dòng rỗng được phép:

ABCA
ACBA

def lcs_length(s, t):
    dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
    for i in range(1, len(s) + 1):
        for j in range(1, len(t) + 1):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[len(s)][len(t)]

s = input()
t = input()
print(lcs_length(s, t))

3

Thứ tự đi từ trên xuống dưới và trái sang phải đảm bảo cả ba ô cần thiết đã được tính. Với độ dài n và m, có n × m ô trong phần thân. Mỗi ô mất O(1), nên thời gian là O(nm) và bộ nhớ là O(nm). Hai chuỗi dài 1 000 ký tự tạo một triệu ô thân; chuỗi dài 100 000 ký tự tạo mười tỉ ô và không phù hợp cách này.

Trong bảng trên, giá trị của một ô không thể giảm khi kéo dài thêm một tiền tố. Ta có thể bỏ qua ký tự vừa thêm và giữ nguyên dãy con cũ. Điều này giúp phát hiện một số lỗi khi đọc bảng, nhưng chưa đủ chứng minh toàn bộ bảng đúng. Ví dụ, một bảng toàn số 0 cũng không giảm mà vẫn sai khi có ký tự chung.

Với hai chuỗi "AAA" và "AA", đáp án là hai chứ không phải sáu. Có nhiều cách chọn vị trí tạo ra cùng dãy "AA", nhưng LCS trong bài đo độ dài. Đừng cộng tất cả các cặp ký tự bằng nhau. Nếu đề hỏi số cách chọn, trạng thái và cách tránh đếm trùng cần được thiết kế riêng.

bad = [[0] * 3] * 2
good = [[0] * 3 for _ in range(2)]
bad[0][1] = 7
good[0][1] = 7
print(bad)
print(good)

[[0, 7, 0], [0, 7, 0]]
[[0, 7, 0], [0, 0, 0]]

Truy vết từ ô cuối dựng lại một đáp án

Nếu chỉ in độ dài thì ô cuối đủ dùng. Nếu cần một dãy, giữ bảng rồi đi từ (n, m) về hàng hoặc cột 0. Khi hai ký tự cuối bằng nhau, ghi lại ký tự và đi chéo. Nếu khác nhau, đi đến ô trên hoặc ô trái có giá trị lớn hơn. Khi hai ô bằng nhau, chọn một phía bất kỳ; đề có thể có nhiều đáp án.

Các ký tự được thu từ cuối về đầu, nên cần đảo trước khi in:

s, t = "ABCA", "ACBA"
n, m = len(s), len(t)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, m + 1):
        if s[i - 1] == t[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
i, j = n, m
answer = []
while i and j:
    if s[i - 1] == t[j - 1]:
        answer.append(s[i - 1])
        i -= 1
        j -= 1
    elif dp[i - 1][j] >= dp[i][j - 1]:
        i -= 1
    else:
        j -= 1
print("".join(reversed(answer)))

ABA

Mỗi bước giảm ít nhất một chỉ số, nên truy vết mất tối đa n + m bước. Độ dài đáp án bằng giá trị ở ô cuối và thứ tự được bảo toàn ở cả hai chuỗi. Quy tắc ưu tiên khi hòa chỉ chọn một đáp án, không bảo đảm đáp án nhỏ nhất theo thứ tự từ điển.

Để kiểm tra một chuỗi được truy vết, hãy kiểm tra ba điều: nó là dãy con của chuỗi đầu, là dãy con của chuỗi sau, và độ dài bằng ô cuối. Không nên so sánh duy nhất với một chuỗi đáp án mẫu nếu đề chấp nhận bất kỳ LCS nào. Chẳng hạn "ABA" và "ACA" đều là LCS của "ABCA" và "ACBA". Chúng khác nhau nhưng đều dài ba và giữ đúng thứ tự.

Hai hàng đủ khi chỉ cần độ dài

Mỗi ô LCS chỉ cần hàng trước và ô ngay bên trái trong hàng hiện tại. Vì vậy, sau khi xong một hàng, ta có thể bỏ hàng cũ hơn. Đặt chuỗi ngắn hơn trên trục cột để dùng O(min(n, m)) bộ nhớ.

def lcs_two_rows(s, t):
    if len(t) > len(s):
        s, t = t, s
    prev = [0] * (len(t) + 1)
    for x in s:
        cur = [0] * (len(t) + 1)
        for j, y in enumerate(t, 1):
            if x == y:
                cur[j] = prev[j - 1] + 1
            else:
                cur[j] = max(prev[j], cur[j - 1])
        prev = cur
    return prev[-1]

print(lcs_two_rows("BANANA", "ATANA"))
print(lcs_two_rows("", "ABC"))

4
0

Thời gian vẫn là O(nm). Cách này không giữ đủ bảng để truy vết trực tiếp bằng các bước ở trên. Nếu sửa một hàng tại chỗ, phải lưu riêng giá trị chéo cũ trước khi ghi đè.

Chuỗi con chung liên tiếp phải kết thúc tại hai vị trí đang xét

Với chuỗi con chung dài nhất, đặt end[i][j] là độ dài đoạn chung liên tiếp kết thúc tại s[i - 1] và t[j - 1]. Nếu hai ký tự khớp, nối đoạn chéo bằng end[i - 1][j - 1] + 1. Nếu khác, đoạn kết thúc tại đó có độ dài 0. Đáp án là giá trị lớn nhất trên toàn bảng, không nhất thiết là ô cuối.

s, t = "ABCD", "ACD"
prev = [0] * (len(t) + 1)
best = 0
for x in s:
    cur = [0] * (len(t) + 1)
    for j, y in enumerate(t, 1):
        if x == y:
            cur[j] = prev[j - 1] + 1
            best = max(best, cur[j])
    prev = cur
print(best)

2

Đoạn "CD" dài hai. Dãy con chung "ACD" dài ba, nhưng không liên tiếp trong "ABCD". Mỗi đoạn chung kết thúc ở một cặp vị trí, nên xét hết các ô sẽ không bỏ sót đáp án. Chi phí là O(nm) thời gian và O(m) bộ nhớ với hai hàng.

Hãy xét thêm s = "ABX" và t = "ABY". Đoạn chung tốt nhất là "AB", nhưng ô cuối của bảng bằng 0 vì X khác Y. Biến best lưu giá trị lớn nhất đã gặp trước khi vòng lặp đi đến ô cuối. Nếu cả hai chuỗi không có ký tự chung, best giữ giá trị 0.

Khoảng cách chỉnh sửa xét thao tác cuối cùng

Khoảng cách chỉnh sửa (edit distance) ở đây là số thao tác ít nhất để biến a thành b. Một thao tác là chèn, xóa hoặc thay một ký tự; mỗi thao tác có giá 1. Giữ nguyên một ký tự không tốn thao tác. Không tính hoán đổi hai ký tự kề là một thao tác riêng.

Đặt dist[i][j] là số thao tác ít nhất đổi a[:i] thành b[:j]. Cột 0 bằng i vì phải xóa hết; hàng 0 bằng j vì phải chèn đủ j ký tự. Tại ô còn lại, xét thao tác cuối: xóa từ ô trên, chèn từ ô trái, hoặc giữ/thay từ ô chéo.

Mọi cách sửa có thể xét theo thao tác cuối liên quan tới ký tự cuối; ba lựa chọn bao phủ các trường hợp đó. Mỗi lựa chọn nối một lời giải tối ưu của tiền tố nhỏ hơn, nên lấy giá trị nhỏ nhất cho lời giải tối ưu. Với CAT và CUT, thay A bằng U là đủ.

Trong bảng, ô của CA và CU có ba ứng viên. Xóa A xuất phát từ ô C và CU; chèn U xuất phát từ ô CA và C. Phép thay A thành U xuất phát từ ô C và C. Hai tiền tố C giống nhau, nên ô chéo bằng 0; thêm một phép thay cho chi phí 1.

Điều quan trọng là mỗi ứng viên mô tả một phép sửa trên lời giải của tiền tố trước đó. Không cộng thêm một khi hai ký tự cuối đã bằng nhau. Nếu đề cho giá chèn, xóa, thay khác nhau, thay các số cộng tương ứng và kiểm tra lại hai hàng biên. Công thức này không tự hỗ trợ một thao tác mới như hoán đổi hai ký tự.

Ví dụ đổi A thành B, với giá chèn 2, xóa 3 và thay 9. Hàng biên ứng với chuỗi nguồn rỗng dùng giá chèn; cột biên ứng với chuỗi đích rỗng dùng giá xóa:

a, b = "A", "B"
ci, cd, cr = 2, 3, 9
prev = [j * ci for j in range(len(b) + 1)]
print("Hàng biên:", prev)
for i, x in enumerate(a, 1):
    cur = [i * cd] + [0] * len(b)
    for j, y in enumerate(b, 1):
        cost = 0 if x == y else cr
        cur[j] = min(prev[j] + cd, cur[j - 1] + ci,
                     prev[j - 1] + cost)
    print("Cột biên:", cur[0])
    prev = cur
print("Chi phí nhỏ nhất:", prev[-1])

Hàng biên: [0, 2]
Cột biên: 3
Chi phí nhỏ nhất: 5

Chọn xóa rồi chèn tốn 5, rẻ hơn thay một lần tốn 9. Đổi chiều hai chuỗi có thể làm kết quả khác khi ci và cd khác nhau. Ví dụ, từ chuỗi rỗng sang A tốn 2, còn chiều ngược lại tốn 3.

def edit_distance(a, b):
    prev = list(range(len(b) + 1))
    for i, x in enumerate(a, 1):
        cur = [i] + [0] * len(b)
        for j, y in enumerate(b, 1):
            cur[j] = min(prev[j] + 1, cur[j - 1] + 1,
                         prev[j - 1] + (x != y))
        prev = cur
    return prev[-1]

print(edit_distance("CAT", "CUT"))
print(edit_distance("", "ABC"))
print(edit_distance("AB", "BA"))

1
3
2

Trường hợp cuối cần hai thao tác theo quy tắc của bài. Nếu chỉ cho chèn và xóa, công thức theo LCS là n + m - 2 * LCS. Công thức đó không tính đúng khi thay một ký tự chỉ tốn một thao tác. Thời gian là O(nm); hai hàng dùng O(m) bộ nhớ.

Dãy con đối xứng được tính từ hai đầu đoạn

Một dãy con đối xứng (palindromic subsequence) đọc từ trái sang phải hay từ phải sang trái đều giống nhau. Đặt dp[l][r] là độ dài lớn nhất trong đoạn s[l:r + 1]. Một ký tự cho giá trị 1; đoạn rỗng cho giá trị 0.

Nếu hai đầu bằng nhau, một đáp án tối ưu có thể dùng cả hai đầu, thêm hai vào đáp án bên trong. Nếu hai đầu khác nhau, ít nhất một đầu không thể cùng xuất hiện ở hai đầu đáp án. Lấy giá trị lớn hơn khi bỏ đầu trái hoặc đầu phải. Độ dài đoạn tăng dần đảm bảo các đoạn ngắn hơn đã được tính.

s = "BANANA"
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n):
    dp[i][i] = 1
for length in range(2, n + 1):
    for left in range(n - length + 1):
        right = left + length - 1
        if s[left] == s[right]:
            inside = dp[left + 1][right - 1] if length > 2 else 0
            dp[left][right] = inside + 2
        else:
            dp[left][right] = max(dp[left + 1][right], dp[left][right - 1])
print(dp[0][n - 1] if n else 0)

5

Ví dụ có dãy "ANANA". Với n = 1 000, bảng có một triệu ô và thời gian O(n²). Trường hợp chuỗi rỗng phải xử lý trước khi truy cập dp[0][n - 1].

Nếu bài hỏi số ký tự ít nhất phải xóa để chuỗi còn lại đối xứng, gọi độ dài dãy đối xứng dài nhất là L. Giữ dãy đó cần xóa n - L ký tự. Mọi kết quả sau khi xóa đều là một dãy con đối xứng, nên không thể giữ nhiều hơn L ký tự. Vì vậy không có cách nào xóa ít hơn n - L.

Lỗi thường gặp

Tóm tắt

• Tiền tố dài i kết thúc ở chỉ số i - 1; tiền tố rỗng nằm ở hàng hoặc cột 0.
• LCS cho phép bỏ ký tự; chuỗi con chung yêu cầu liên tiếp và cần lấy giá trị lớn nhất toàn bảng.
• Khoảng cách chỉnh sửa xét chèn, xóa, thay hoặc giữ; mỗi thao tác có chi phí theo đề.
• Lưu hai hàng giúp giảm bộ nhớ khi chỉ cần giá trị; truy vết thông thường cần giữ bảng.
• Trạng thái theo đoạn giúp tính dãy con đối xứng, với O(n²) thời gian và bộ nhớ.

Kiểm tra nhanh

Đọc thêm

• Tài liệu Python: kiểu chuỗi và lát cắt.
• Tài liệu Python: danh sách.