[Mỗi ngày 1 thuật toán] Tính độ dài đoạn chuỗi chung dài nhất

Tiếp nỗi chuỗi series “Mỗi ngày 1 thuật toán” là bài toán Tính độ dài đoạn chuỗi chung dài nhất giữa hai chuỗi. Để 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. 

1. Ý tưởng chính của bài toán tính độ dài đoạn chuỗi chung dài nhất

• Đề bài: Cho 2 chuỗi string1 và string2. Hãy tìm độ dài của đoạn chuỗi chung dài nhất giữa hai chuỗi này.
• Ý tưởng: Sử dụng một mảng 2 chiều có kích thước của mỗi chiều tương đương với độ dài của hai mảng string1 và string2. Mảng này sẽ lưu trữ độ dài của các chuỗi chung ở từng vị trí.

2. Ví dụ minh hoạ của bài toán tính độ dài chuỗi chung

• Hai chuỗi string1 = “ABCDGH” và string2 = “ACDGHR”
• Đoạn chuỗi chung dài nhất là “CDGH”

Như vậy, độ dài của đoạn chuỗi chung dài nhất là 4. 

3. Mã nguồn dạng Pseudo-code của bài toán tính độ dài chuỗi chung

4. Mã nguồn Java của bài toán tính độ dài chuỗi chung

5. Mã nguồn PHP của bài toán tính độ dài chuỗi chung

6. Mã nguồn Python của bài toán tính độ dài chuỗi chung

Xem thêm các bài viết thú vị về Thuật toán tại đây!