[Mỗi ngày một thuật toán] Bài toán Tìm chuỗi con chung dài nhất

Bạn đã bao giờ tự hỏi làm thế nào để tìm ra phần giống nhau dài nhất giữa hai chuỗi ký tự? Bài toán “Tìm chuỗi con chung dài nhất” sẽ tiếp nối cho chuỗi chủ đề “Mỗi ngày 1 thuật toán” của CodeGym.

Trong bài viết này, chúng ta sẽ khám phá cách tiếp cận hiệu quả để giải quyết bài toán LCS. Từ giải thuật đơn giản đến tối ưu hóa bằng quy hoạch động, bạn sẽ học được cách xây dựng một giải pháp mạnh mẽ cho vấn đề này. Để giải bài toán này, CodeGym sẽ cung cấp cho bạn ba đoạn mã nguồn quan trọng, bao gồm: Java, PHP và Python. 

Mô tả bài toán

Cho hai chuỗi, hãy tìm chiều dài của chuỗi con chung dài nhất (Longest Common Subsequence – LCS). Một chuỗi con là một dãy các ký tự xuất hiện theo cùng thứ tự như trong chuỗi ban đầu, nhưng không cần phải liên tiếp.

Ví dụ

Đầu vào: “ABCBDAB” và “BDCAB”
Đầu ra: 4 (Chuỗi con chung dài nhất là “BCAB” hoặc “BDAB”)

1. Pseudo-code

2. Mã nguồn Java

3. Mã nguồn PHP

4. Mã nguồn Python

Nếu thay đổi định nghĩa của chuỗi con, yêu cầu các ký tự phải xuất hiện liên tiếp nhau, thì thuật toán này cần phải thay đổi như thế nào?