Xâu con chung dài nhất (LCS)

Mức độ: Nâng cao

Hai xâu ABCBDAB và BDCABA có chung những dãy con nào? Ví dụ BCBA (xóa bớt ký tự ở mỗi xâu mà vẫn giữ thứ tự). Dài nhất là 4. Bài xâu con chung dài nhất (LCS) là bài mẫu của quy hoạch động trên hai xâu: trạng thái là một cặp tiền tố, một tiền tố của mỗi xâu.

Bảng quy hoạch động

Gọi f[i][j] là độ dài xâu con chung dài nhất của i ký tự đầu của s và j ký tự đầu của t. Xét ký tự cuối s_i và t_j:

• giống nhau: dùng cặp này làm ký tự cuối của xâu chung, f[i][j] = f[i - 1][j - 1] + 1;
• khác nhau: ít nhất một trong hai ký tự không thuộc xâu chung, bỏ nó đi: f[i][j] = max(f[i - 1][j], f[i][j - 1]).

Hàng 0 và cột 0 bằng 0 (một xâu rỗng). Với s = ABCB, t = BDCB:

		B	D	C	B
	0	0	0	0	0
A	0	0	0	0	0
B	0	1	1	1	1
C	0	1	1	2	2
B	0	1	1	2	3

Đáp số ở góc dưới phải là 3 (xâu BCB). Bảng có (n + 1) × (m + 1) ô, mỗi ô một phép tính: với n = m = 3000 là khoảng 9 × 10⁶ bước.

Python

s = input().strip()
t = input().strip()
n, m = len(s), len(t)
truoc = [0] * (m + 1)                 # hàng i - 1
for i in range(1, n + 1):
    hien_tai = [0] * (m + 1)          # hàng i
    for j in range(1, m + 1):
        if s[i - 1] == t[j - 1]:
            hien_tai[j] = truoc[j - 1] + 1
        else:
            hien_tai[j] = max(truoc[j], hien_tai[j - 1])
    truoc = hien_tai
print(truoc[m])

C++

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    string s, t;
    cin >> s >> t;
    int n = s.size(), m = t.size();
    vector<int> truoc(m + 1, 0), hienTai(m + 1, 0);    // hàng i - 1 và hàng i
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s[i - 1] == t[j - 1]) hienTai[j] = truoc[j - 1] + 1;
            else hienTai[j] = max(truoc[j], hienTai[j - 1]);
        }
        swap(truoc, hienTai);
    }
    cout << truoc[m] << "\n";
    return 0;
}

Mỗi hàng chỉ cần hàng ngay trên, nên chỉ giữ hai hàng thay vì cả bảng: bộ nhớ m thay vì n × m.

Truy vết

Muốn in ra xâu chung (không chỉ độ dài) thì cần cả bảng. Đi từ góc (n, m) ngược về: nếu s_i = t_j thì ký tự này thuộc xâu chung, lùi chéo về (i - 1, j - 1); nếu không thì lùi về ô có giá trị bằng f[i][j] (ô trên hoặc ô trái). Các ký tự gặp được, đọc ngược lại, là xâu chung.

Khoảng cách sửa xâu

Biến xâu s thành t bằng ba thao tác chèn, xóa, thay một ký tự. Số thao tác ít nhất gọi là khoảng cách sửa xâu. Cùng kiểu bảng, g[i][j] là số thao tác ít nhất biến i ký tự đầu của s thành j ký tự đầu của t:

• s_i = t_j: g[i][j] = g[i - 1][j - 1] (không cần làm gì với cặp cuối);
• ngược lại: g[i][j] = 1 + min(g[i - 1][j] (xóa s_i), g[i][j - 1] (chèn t_j), g[i - 1][j - 1] (thay s_i bằng t_j)).

Hàng 0 là g[0][j] = j (chèn j ký tự), cột 0 là g[i][0] = i (xóa i ký tự).

Nhiều bài, một khuôn

Đề hỏi	Cách đưa về LCS hoặc bảng hai xâu
xóa ít nhất để hai xâu bằng nhau	n + m - 2 × LCS
xâu ngắn nhất chứa cả hai làm dãy con	n + m - LCS
dãy con đối xứng dài nhất của s	LCS của s và s đảo ngược
xâu con chung liên tiếp dài nhất	f[i][j] = f[i - 1][j - 1] + 1 nếu giống, 0 nếu khác

Luyện tập

Gồm 16 bài, chia thành 4 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.

Nhóm 1. Xâu con chung dài nhất

Bài 1. Độ dài xâu con chung dài nhất

Nhập hai xâu s, t trên hai dòng, gồm chữ cái in hoa, mỗi xâu dài từ 1 đến 3000. In ra độ dài xâu con chung dài nhất (dãy con, không cần liên tiếp).

Ví dụ:

Nhập	In ra
ABCBDAB BDCABA	4

Kiểm tra: nhập

THEQUICKBROWNFOX
JUMPSOVERTHELAZYDOG

Xem đáp số

4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 2. Xóa ít nhất để hai xâu bằng nhau

Nhập hai xâu s, t trên hai dòng (chữ cái thường, mỗi xâu dài từ 1 đến 3000). Mỗi bước được xóa một ký tự của s hoặc của t. In ra số bước ít nhất để hai xâu bằng nhau.

Ví dụ:

Nhập	In ra
sea eat	2

Kiểm tra: nhập

bumbiiacademy
academicbumbii

Xem đáp số

15

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. Xâu ngắn nhất chứa cả hai

Nhập hai xâu s, t trên hai dòng (chữ cái thường, mỗi xâu dài từ 1 đến 3000). In ra độ dài xâu ngắn nhất mà cả s và t đều là dãy con của nó.

Ví dụ:

Nhập	In ra
abac cab	5

Kiểm tra: nhập

programming
gaming

Xem đáp số

11

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 4. Dãy con chung của hai dãy số

Dòng đầu có n, m (1 ≤ n, m ≤ 3000), dòng thứ hai có n số của dãy A, dòng thứ ba có m số của dãy B (|giá trị| ≤ 10⁹). In ra độ dài dãy con chung dài nhất của A và B.

Ví dụ:

Nhập	In ra
6 5 1 3 4 1 2 1 3 4 1 2 1	5

Kiểm tra: nhập

8 9
5 -1 7 7 3 0 2 9
7 5 3 -1 9 0 2 7 9

Xem đáp số

5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 5. In xâu con chung dài nhất

Nhập hai xâu s, t trên hai dòng (chữ cái thường, mỗi xâu dài từ 1 đến 1000). In ra một xâu con chung dài nhất; nếu có nhiều, in xâu nhỏ nhất theo thứ tự từ điển. Nếu không có ký tự chung, in ra dòng -.

Ví dụ:

Nhập	In ra
abcab bacba	aba

Kiểm tra: nhập

bumbiiacademy
academicbumbii

Xem đáp số

academ

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 2. Đối xứng

Bài 6. Dãy con đối xứng dài nhất

Nhập một xâu s (chữ cái thường, 1 ≤ độ dài ≤ 3000). In ra độ dài dãy con (không cần liên tiếp) dài nhất của s đọc xuôi và đọc ngược như nhau.

Ví dụ: nhập bbbab thì in ra 4.

Kiểm tra: nhập character.

Xem đáp số

5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 7. Chèn ít nhất để đối xứng

Nhập một xâu s (chữ cái thường, 1 ≤ độ dài ≤ 3000). Mỗi bước được chèn một ký tự bất kỳ vào vị trí bất kỳ. In ra số bước ít nhất để s thành xâu đối xứng.

Ví dụ: nhập mbadm thì in ra 2.

Kiểm tra: nhập leetcode.

Xem đáp số

5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 8. Đoạn đối xứng dài nhất

Nhập một xâu s (chữ cái thường, 1 ≤ độ dài ≤ 5000). In ra độ dài đoạn ký tự liên tiếp dài nhất của s là xâu đối xứng.

Ví dụ: nhập babad thì in ra 3.

Kiểm tra: nhập forgeeksskeegfor.

Xem đáp số

10

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 3. Sửa xâu và khớp mẫu

Bài 9. Khoảng cách sửa xâu

Nhập hai xâu s, t trên hai dòng (chữ cái thường, mỗi xâu dài từ 1 đến 3000). Mỗi bước được chèn, xóa hoặc thay một ký tự của s. In ra số bước ít nhất để biến s thành t.

Ví dụ:

Nhập	In ra
horse ros	3

Kiểm tra: nhập

intention
execution

Xem đáp số

5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 10. Sửa xâu với chi phí khác nhau

Dòng đầu có ba số c_chèn, c_xóa, c_thay (1 ≤ mỗi số ≤ 1000): chi phí chèn, xóa, thay một ký tự. Hai dòng sau là s và t (chữ cái thường, mỗi xâu dài từ 1 đến 3000). In ra tổng chi phí ít nhất để biến s thành t.

Ví dụ:

Nhập	In ra
1 1 3 abc adc	2

Kiểm tra: nhập

2 3 4
kitten
sitting

Xem đáp số

10

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 11. Khớp mẫu có ký tự đại diện

Dòng đầu là mẫu p gồm chữ cái thường và hai ký tự đặc biệt: ? khớp với đúng một ký tự bất kỳ, * khớp với một dãy bất kỳ (kể cả rỗng). Dòng thứ hai là xâu s gồm chữ cái thường. Mỗi xâu dài từ 1 đến 2000. In ra YES nếu p khớp với toàn bộ s, ngược lại NO.

Ví dụ:

Nhập	In ra
a*b?d axxbcd	YES

Kiểm tra: nhập

*ab*?c
xabyyzc

Xem đáp số

YES

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 12. Trộn hai xâu

Nhập ba xâu a, b, c trên ba dòng (chữ cái thường; a, b dài từ 1 đến 2000). In ra YES nếu c được tạo bằng cách trộn a và b: lấy lần lượt các ký tự của a và b, giữ nguyên thứ tự trong mỗi xâu, xen kẽ tùy ý. Ngược lại in NO.

Ví dụ:

Nhập	In ra
aab axy aaxaby	YES

Kiểm tra: nhập

abc
def
adbecf

Xem đáp số

YES

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 13. Đếm số cách xóa

Nhập hai xâu s, t trên hai dòng (chữ cái thường, 1 ≤ |s| ≤ 3000, 1 ≤ |t| ≤ 1000). In ra số cách chọn các vị trí trong s (theo thứ tự tăng dần) để các ký tự ở đó tạo thành t, chia lấy dư 10⁹ + 7.

Ví dụ:

Nhập	In ra
rabbbit rabbit	3

Kiểm tra: nhập

babgbagbag
bag

Xem đáp số

13

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 4. Mở rộng

Bài 14. Đoạn chung dài nhất

Nhập hai xâu s, t trên hai dòng (chữ cái thường, mỗi xâu dài từ 1 đến 3000). In ra độ dài đoạn ký tự liên tiếp dài nhất xuất hiện trong cả hai xâu.

Ví dụ:

Nhập	In ra
abcdxyz xyzabcd	4

Kiểm tra: nhập

bumbiiacademy
academicbumbii

Xem đáp số

6

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 15. Dãy con chung của ba xâu

Nhập ba xâu trên ba dòng (chữ cái thường, mỗi xâu dài từ 1 đến 150). In ra độ dài dãy con chung dài nhất của cả ba xâu.

Ví dụ:

Nhập	In ra
abcd acbd abd	3

Kiểm tra: nhập

geeksforgeeks
geeksquiz
geeksforgeeksquiz

Xem đáp số

5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 16. Dãy con chung khi một dãy là hoán vị

Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), hai dòng sau là hai hoán vị P và Q của 1, 2, …, n. In ra độ dài dãy con chung dài nhất của P và Q.

Ví dụ:

Nhập	In ra
5 1 3 2 5 4 3 1 5 2 4	3

Kiểm tra: nhập

10
4 7 1 9 3 10 2 6 8 5
7 4 9 1 10 3 6 2 5 8

Xem đáp số

5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Lời giải chi tiết các bài luyện tập

Đáp số của từng bài ở ngay dưới đề để các bạn tự kiểm tra. Lời giải chi tiết (phân tích, chạy tay, chương trình Python và C++, lưu ý khi làm bài) có trong bộ tài liệu có phí của chuyên đề.

Thầy cô và các bạn muốn mua bộ tài liệu vui lòng liên hệ tác giả qua Zalo 0972465159 hoặc Facebook.