Longest Common Substring

Q: Độ phức tạp thời gian của bài toán tìm chuỗi con chung dài nhất là bao nhiêu?

Lời giải bằng quy hoạch động mất thời gian O(n × m) và dùng O(m) bộ nhớ với một hàng duy nhất. Mở rộng từ mọi cặp vị trí bắt đầu có độ phức tạp O(n × m × min(n, m)) trong trường hợp xấu nhất. Máy tự động hậu tố đạt độ phức tạp khoảng O(n + m) , đổi lại là chương trình dài hơn nhiều.

Q: Làm thế nào để trả về chính chuỗi con chung dài nhất?

Mỗi khi một ô có giá trị lớn hơn best , hãy ghi lại vị trí i trong s1 nơi khối đó kết thúc. Cuối cùng, chuỗi con gồm best ký tự của s1 kết thúc tại đó. Phép so sánh lớn hơn nghiêm ngặt giúp giữ lại khối dài nhất đầu tiên được tìm thấy trong s1 .

Trung bìnhQuy hoạch động

+10

Bạn nhận được hai chuỗi, s1 và s2. Chuỗi con là một dãy chữ cái liền nhau được lấy từ một chuỗi, chẳng hạn như ork trong clockwork. Hãy tìm chuỗi con dài nhất mà s1 và s2 cùng có, rồi trả về độ dài của chuỗi đó. Nếu không có chữ cái nào xuất hiện trong cả hai chuỗi, đáp án là 0.

Hàm

longestCommonSubstring(s1: string, s2: string) → integer

s1string: chuỗi đầu tiên
s2string: chuỗi thứ hai
Trả vềinteger: độ dài của khối chữ cái dài nhất có trong cả hai chuỗi

Ràng buộc

1 ≤ s1.length ≤ 1000
1 ≤ s2.length ≤ 1000
s1 và s2 gồm các chữ cái tiếng Anh viết thường.

Ví dụ

Đầu vào: s1 = "clockwork"s2 = "workshop"
Đầu ra: 4
Giải thích: work đóng clockwork và mở workshop, nên đây là chuỗi con chung có độ dài 4, và không có khối dài hơn nào xuất hiện trong cả hai.

Đầu vào: s1 = "hammer"s2 = "harmed"
Đầu ra: 2
Giải thích: ha và me xuất hiện trong cả hai từ, nhưng không có chuỗi gồm ba chữ cái nào xuất hiện trong cả hai từ. Cả hai từ đều chứa h, a, m, e theo thứ tự đó, nhưng harmed có chữ r nằm giữa a và m.

Câu hỏi mở rộng

Bạn có thể kiểm tra xem có tồn tại chuỗi con chung có độ dài L hay không trong khoảng O(n + m) thời gian bằng hàm băm cuộn, rồi tìm kiếm nhị phân theo L không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Mở rộng một đoạn khớp từ mọi cặp điểm bắt đầu sẽ đọc lại cùng những chữ cái. Thay vào đó, hãy xem một khối kết thúc ở đâu: khối chung kết thúc tại s1[i] và s2[j] dài hơn một chữ cái so với khối kết thúc tại hai chữ cái đứng ngay trước chúng, hoặc rỗng nếu hai chữ cái khác nhau. Một bảng lưu các độ dài này sẽ cho kết quả trong thời gian O(n × m).

Mở rộng từ mọi cặp vị trí bắt đầu

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Mọi chuỗi con chung đều bắt đầu ở một vị trí i trong s1 và một vị trí j trong s2. Với mỗi cặp, hãy tiến lần lượt từng ký tự khi các chữ cái trùng nhau và đếm số bước; số đếm lớn nhất là đáp án.

Văn bản lặp lại khiến các lượt kiểm tra kéo dài. Khi cả hai chuỗi đều gồm 1000 bản sao của a, mỗi cặp sẽ đi đến cuối hậu tố ngắn hơn: khoảng 3.3 × 10^8 lần so sánh ký tự. Lượt kiểm tra bắt đầu từ (i, j) lặp lại toàn bộ lượt kiểm tra từ (i+1, j+1), chỉ trễ hơn một ký tự.

Thuật toán

Đặt best = 0.
Với mỗi i trong s1 và mỗi j trong s2, đặt k = 0.
Trong khi cả i+k và j+k đều nằm trong chuỗi của chúng và s1[i+k] == s2[j+k], hãy cộng 1 vào k.
Giữ giá trị k lớn nhất trong best và trả về giá trị đó.

def longestCommonSubstring(s1, s2):
    n, m = len(s1), len(s2)
    best = 0
    for i in range(n):
        for j in range(m):
            # Walk forward while the two strings agree
            k = 0
            while i + k < n and j + k < m and s1[i + k] == s2[j + k]:
                k += 1
            if k > best:
                best = k
    return best

Bảng độ dài khối kết thúc tại từng cặp

Ý tưởng

Gọi run[i][j] là độ dài của khối chung dài nhất kết thúc chính xác tại s1[i-1] và s2[j-1]; hàng 0 và cột 0 chứa giá trị 0. Khối như vậy phải chứa cả hai chữ cái. Nếu chúng khác nhau, không có khối nào và ô đó có giá trị 0. Nếu chúng giống nhau, khối này gồm cặp chữ cái đó cộng với khối kết thúc sớm hơn một chữ cái trong cả hai chuỗi: run[i-1][j-1] + 1. Mọi chuỗi con chung đều kết thúc ở đâu đó, nên đáp án là ô có giá trị lớn nhất, bất kể nó nằm ở đâu.

Với hammer và harmed, hai chữ h cho giá trị 1, hai chữ a kéo dài khối lên 2, rồi chữ r làm khối bị ngắt. Chữ m thứ hai trong hammer gặp chữ m trong harmed sau khi m và r không khớp, nên khối bắt đầu từ 1; hai chữ e nâng giá trị lên 2. Không ô nào đạt đến 3.

Mỗi ô cần một lần so sánh: khoảng một triệu lần với hai chuỗi gồm 1000 chữ cái, bất kể nội dung văn bản.

Thuật toán

Cấp phát run với n+1 hàng và m+1 cột, tất cả đều bằng 0, rồi đặt best = 0.
Lặp i từ 1..n và bên trong lặp j từ 1..m, so sánh s1[i-1] với s2[j-1].
Nếu khớp, đặt run[i][j] = run[i-1][j-1] + 1 và cập nhật best.
Nếu không khớp, giữ ô đó ở giá trị 0.
Trả về best.

def longestCommonSubstring(s1, s2):
    n, m = len(s1), len(s2)
    # run[i][j]: length of the longest block that ends at s1[i-1] and at s2[j-1]
    run = [[0] * (m + 1) for _ in range(n + 1)]
    best = 0
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if s1[i - 1] == s2[j - 1]:
                run[i][j] = run[i - 1][j - 1] + 1
                if run[i][j] > best:
                    best = run[i][j]
            # a mismatch leaves run[i][j] at 0
    return best

Một hàng, được cập nhật từ phải sang trái

Ý tưởng

Mỗi ô chỉ đọc ô chéo lên trên và sang trái. Vì vậy, một mảng run gồm m+1 số có thể lưu bảng nếu bạn duyệt j từ phải sang trái: khi ghi run[j], ô run[j-1] vẫn giữ giá trị của ký tự trước đó trong s1, tức là ô chéo.

Bây giờ, khi hai ký tự không khớp, bạn phải ghi rõ giá trị 0 vì ô đó vẫn chứa một số từ hàng trước. Thời gian vẫn là O(n × m), còn bộ nhớ giảm từ khoảng 10^6 số xuống còn 1001.

Thuật toán

Tạo một mảng run gồm m+1 số 0 và đặt best = 0.
Với mỗi ký tự ch trong s1, duyệt j từ m giảm dần đến 1.
Nếu ch == s2[j-1], đặt run[j] = run[j-1] + 1 và cập nhật best.
Nếu không, đặt run[j] = 0.
Trả về best.

def longestCommonSubstring(s1, s2):
    m = len(s2)
    # run[j]: length of the common block that ends at the current letter of s1 and at s2[j-1]
    run = [0] * (m + 1)
    best = 0
    for ch in s1:
        # Right to left, so run[j-1] still holds the value from the previous letter of s1
        for j in range(m, 0, -1):
            if ch == s2[j - 1]:
                run[j] = run[j - 1] + 1
                if run[j] > best:
                    best = run[j]
            else:
                run[j] = 0
    return best

Lỗi thường gặp và trường hợp biên

Trả về ô cuối cùng. run[n][m] chỉ tính những khối kết thúc ở cả chữ cái cuối cùng của mỗi chuỗi. Với abc và abd, giá trị là 0, còn với ab thì là 2.
Sao chép giá trị lớn hơn ở ô lân cận khi hai ký tự không khớp. Đó là quy tắc của dãy con, cho phép một khối bỏ qua các chữ cái: với hammer và harmed, cách này cho kết quả 4 thay vì 2.
Duyệt hàng duy nhất từ trái sang phải. Giá trị trên đường chéo bị ghi đè trước khi bạn đọc nó, nên so sánh a với aa cho kết quả 2.
Bỏ qua bước đặt lại trong hàng duy nhất. Độ dài từ ký tự trước đó của s1 vẫn còn và sau đó kéo dài một khối không tồn tại.
Duyệt cách vét cạn mà không kiểm tra giới hạn. Khi so sánh zzzz với zz, chương trình đọc quá cuối chuỗi ngắn hơn.

Câu hỏi thường gặp3

Sự khác nhau giữa chuỗi con chung dài nhất và dãy con chung dài nhất là gì?

Chuỗi con là một đoạn ký tự liên tiếp không bị ngắt; dãy con giữ nguyên thứ tự nhưng có thể bỏ qua một số ký tự. Với hammer và harmed, chuỗi con chung dài nhất có độ dài 2, còn dãy con chung dài nhất có độ dài 4 (hame). Trong các bảng, khi hai ký tự không khớp, ô chuỗi con được đặt lại thành 0, còn ô dãy con sao chép giá trị lớn hơn trong hai ô bên cạnh.

Độ phức tạp thời gian của bài toán tìm chuỗi con chung dài nhất là bao nhiêu?

Lời giải bằng quy hoạch động mất thời gian O(n × m) và dùng O(m) bộ nhớ với một hàng duy nhất. Mở rộng từ mọi cặp vị trí bắt đầu có độ phức tạp O(n × m × min(n, m)) trong trường hợp xấu nhất. Máy tự động hậu tố đạt độ phức tạp khoảng O(n + m), đổi lại là chương trình dài hơn nhiều.

Làm thế nào để trả về chính chuỗi con chung dài nhất?

Mỗi khi một ô có giá trị lớn hơn best, hãy ghi lại vị trí i trong s1 nơi khối đó kết thúc. Cuối cùng, chuỗi con gồm best ký tự của s1 kết thúc tại đó. Phép so sánh lớn hơn nghiêm ngặt giúp giữ lại khối dài nhất đầu tiên được tìm thấy trong s1.

def longestCommonSubstring(s1, s2):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

s1 = "clockwork"
s2 = "workshop"

Đầu ra mong đợi

Longest Common Substring

Hàm

Ràng buộc

Ví dụ

Gợi ý

Lời giải

Mở rộng từ mọi cặp vị trí bắt đầu

Bảng độ dài khối kết thúc tại từng cặp

Một hàng, được cập nhật từ phải sang trái

Lỗi thường gặp và trường hợp biên

Câu hỏi thường gặp3

Bài tập tương tự