Thuật toán tìm dãy con chung dài nhất và lớn nhất về giá trị

Mục tiêu là tìm dãy con chung dài nhất giữa hai chuỗi \(a\) và \(b\), đồng thời đảm bảo dãy con này có giá trị số lớn nhất (khi các ký tự được hiểu như các chữ số). Thuật toán bao gồm các bước sau:

Bước 1: Tìm độ dài của dãy con chung dài nhất (LCS)

Sử dụng kỹ thuật Quy Hoạch Động (Dynamic Programming):

Gọi \(L[i][j]\) là độ dài dãy con chung dài nhất tính từ vị trí \(a[i \dots \text{length}(a)]\) và \(b[j \dots \text{length}(b)]\). Công thức truy hồi:

\( L[i][j] = \max\left( L[i+1][j],\\ L[i][j+1],\\ L[i+1][j+1] + \text{ord}(a[i] = b[j]) \right) \)

Bước 2

• Tìm chữ số ở hàng trái nhất (cao nhất) đó là chữ số \(ch\) có tại vị trí \(i\) trong \(a\) và vị trí \(j\) trong \(b\) mà \(m=L[i,j]\). Đó là độ dài xâu con chung dài nhất \((m)\).

Bước 3

• Tiếp tục tìm các ký tự còn lại của dãy con chung theo trình tự vòng lặp:
• Tìm chữ số \(k=m-1\) tới \(1\) (tính từ phải qua trái)
  • Duyệt chữ số \(ch\) từ lớn đến nhỏ (\(9\) đến \(1\))
    • Cho \(x\) tăng từ \(i+1\) cho đến khi \(a[x]=ch\)
    • Cho \(y\) tăng từ \(j+1\) cho đến khi \(b[y]=ch\)
    • Nếu \(L[x,y]=k\) thì \(ch\) là chữ số ở hàng \(k\) (tính từ phải sang)

Kết quả

Dãy con chung dài nhất và lớn nhất về giá trị được xây dựng qua các bước trên.