Bài 2. Xâu con chung dài nhất

            Xâu S được gọi là xâu con chung của xâu S1 và xâu S2 nếu xâu S là một dãy các ký tự liên tiếp trong S1 và cũng là dãy các ký tự liên tiếp trong S2.
Yêu cầu: Cho hai xâu kí tự S1 và S2 (có không quá 255 ký tự). Hãy tìm độ dài xâu con chung dài nhất S của hai xâu S1 và S2. Ví dụ: S1 = ’Ky thi hoc sinh gioi Tinh mon Tin hoc’, S2 = ’hoc sinh gioi mon Tin hoc’ thì S = ‘hoc sinh gioi  ' và độ dài cần tìm là 14.
Dữ liệu: Vào từ file văn bản Bai2.inp:

• Dòng đầu tiên ghi xâu S1;
• Dòng thứ hai ghi xâu S2.

Kết quả: Ghi ra file văn bản Bai2.out: Chỉ một số duy nhất là độ dài của xâu con chung dài nhất  S. (Nếu hai xâu S1, S2 không có kí tự nào chung thì ghi số 0).
Ví dụ:

Bai2.inp	Bai2.inp
Ky thi hoc sinh gioi Tinh mon tin hoc hoc sinh gioi mon Tin hoc	14

Code mẫu bằng Pascal

Const fi='Bai2.inp';
      fo='Bai2.out';
var S1,S2: string;
    i,j,l1,l2,k,kmax:byte;
procedure doctep;
var f:text;
begin
  assign(f,fi);
  reset(f);
  readln(f,s1);
  readln(f,s2);
 close(f);
end;
procedure capnhat;
begin
  if kmax < k then kmax:=k;
end;
procedure xuly;
begin
  l1:=length(s1);
  l2:=length(s2);
  k:=0;
  kmax:=0;
  for i:=1 to l1 do
    for j:=1 to l2 do
      if s1[i]=s2[j] then
      begin
        k:=1;
        while (i+k<=l1) and (j+k<=l2) and (s1[i+k]=s2[j+k]) do inc(k);
        capnhat;
      end;
end;
procedure ghitep;
var f:text;
begin
  assign(f,fo);
  rewrite(f);
  writeln(f,kmax);
  close(f);
end;
BEGIN
 DOCTEP;
 XULY;
 GHITEP;
END.

Solution

Dùng hai vòng lặp để so sánh các ký tự của chuỗi s1 với tất cả ký tự của chuỗi s2. Nếu chúng bằng nhau thì cho k:=1. Đồng thời dùng vòng while để kiểm tra các phần tử tiếp theo của cả 2 chuỗi có bằng nhau hay không? nếu bằng thì tăng k lên 1. và chạy thủ tục capnhat để tìm kmax, (là độ dài chuỗi dài nhất).

Viết theo quy hoạch động bằng Python

Solution

Để viết theo quy hoạch động ta tạo một mảng 2 chiều dp (Có số cột chính là độ dài của xâu s1; Có số hàng chính là độ dài của xâu s2). Mảng này sẽ lưu lại độ dài của các xâu con chung. Như vậy thì giá trị tạo cột`i`, hàng `j` sẽ là `dp[i][j]` đại diện cho độ dài của xâu con chung liên tiếp dài nhất, kết thúc tại ký tự thứ `i` của xâu `s1` và ký tự thứ `j` của xâu `s2`.  Với mỗi ô `(i, j)` trong ma trận, nếu ký tự tại vị trí `i` của xâu `s1` bằng ký tự tại vị trí `j` của xâu `s2` thì ta gán `dp[i][j] = dp[i-1][j-1] + 1`, tức là tăng giá trị của `dp[i][j]` lên 1 so với ô ở phía trước đó, đồng thời lúc này ta so sánh `dp[i][j]` với `max` để cập nhật lại giá trị `max` để lưu độ dài xâu con chung dài nhất. Nếu không, `dp[i][j]` sẽ bằng 0. Bài toán này không yêu cầu in ra dãy con chung dài nhất nên ta không cần truy vết, lúc đó ta sẽ code như sau:

Code python

# Đọc dữ liệu từ file input
with open("Bai2.inp", "r") as f:
    s1 = f.readline().strip()
    s2 = f.readline().strip()

# Tạo bảng để lưu độ dài của xâu con chung
dp = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]

max=0
# Duyệt qua các phần tử của 2 xâu và tính độ dài xâu con chung tại mỗi ô của bảng
for i in range(1, len(s1) + 1):
    for j in range(1, len(s2) + 1):
        if s1[i - 1] == s2[j - 1]:  # Nếu hai ký tự giống nhau
            dp[i][j] = dp[i - 1][j - 1] + 1  # Cộng thêm 1 vào độ dài của xâu con chung
            if dp[i][j]>max:
                max=dp[i][j] # Cập nhật lại max.

# In ra độ dài của xâu con chung dài nhất
with open("Bai2.out", "w") as f:
    f.write(str(max))

 

Truy vết: Nếu bài toán yêu cầu in ra xâu con chung

Để truy vết ta cần dùng thêm 2 biết lưu vị trí bắt đầu và kết thúc của xâu con chung dài nhất, biến này sẽ thay đổi khi `max` thay đổi. Ta sẽ khởi tạo thêm 2 biến `start_index=None` và `end_index=None`. Và ta sẽ gán `start_index = i - max` và `start_index = i - 1` mỗi khi `max` thay đổi.

Code truy vết bằng python

# Đọc dữ liệu từ file input
with open("Bai2.inp", "r") as f:
    s1 = f.readline().strip()
    s2 = f.readline().strip()

# Tạo bảng để lưu độ dài của xâu con chung
dp = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]

start_index = None  # index bắt đầu của xâu con chung liên tiếp dài nhất
end_index = None  # index kết thúc của xâu con chung liên tiếp dài nhất
max=0   # Độ dài xâu con chung dài nhất
# Duyệt qua các phần tử của 2 xâu và tính độ dài xâu con chung tại mỗi ô của bảng
for i in range(1, len(s1) + 1):
    for j in range(1, len(s2) + 1):
        if s1[i - 1] == s2[j - 1]:  # Nếu hai ký tự giống nhau
            dp[i][j] = dp[i - 1][j - 1] + 1  # Cộng thêm 1 vào độ dài của xâu con chung
            if dp[i][j]>max:
                max=dp[i][j] # Cập nhật lại max
                start_index = i - max
                end_index = i - 1

# In ra độ dài của xâu con chung dài nhất
with open("Bai2.out", "w") as f:
    f.write(str(max))

# In xâu con lớn nhất ra màn hình
if max!=0:
    print(s1[start_index:end_index+1])
else: print('Không co xâu chung nào')

 

Các test

Các test được đính kèm cuối bài viết.