ค้นหาความยาวของลำดับย่อยที่ยาวที่สุดของสตริงหนึ่งซึ่งเป็นสตริงย่อยของสตริงอื่นใน C++

สมมติว่าเรามีสตริง X และ Y สองสตริง และเราต้องหาความยาวของลำดับย่อยที่ยาวที่สุดของสตริง X ซึ่งเป็นสตริงย่อยในลำดับ Y ดังนั้นหาก X ="ABCD" และ Y ="BACDBDCD" ผลลัพธ์จะเป็น 3 เนื่องจาก “ACD” เป็นลำดับย่อยที่ยาวที่สุดของ X ซึ่งเป็นสตริงย่อยของ Y

ที่นี่เราจะใช้แนวทางการเขียนโปรแกรมแบบไดนามิกเพื่อแก้ปัญหานี้ ดังนั้นหากความยาวของ X คือ n และความยาวของ Y คือ m ให้สร้างอาร์เรย์ DP ของลำดับ (m+1)x(n+1) ค่าของ DP[i, j] คือความยาวสูงสุดของลำดับรองของ X[0…j] ซึ่งเป็นสตริงย่อยของ Y[0…i] ตอนนี้สำหรับแต่ละเซลล์ของ DP จะมีดังต่อไปนี้:

• สำหรับ i ในช่วง 1 ถึง m:
  • สำหรับ j ในช่วง 1 ถึง n
    • เมื่อ X[i – 1] เหมือนกับ Y[j – i] แล้ว DP[i, j] :=1 + DP[i – 1, j – 1]
    • มิฉะนั้น DP[i, j] :=1 + DP[i, j – 1]

และสุดท้าย ความยาวของลำดับย่อยที่ยาวที่สุดของ x ซึ่งเป็นสตริงย่อยของ y คือ max(DP[i, n]) โดยที่ 1 <=i <=m.

ตัวอย่าง

#include<iostream>
#define MAX 100
using namespace std;
int maxSubLength(string x, string y) {
   int table[MAX][MAX];
   int n = x.length();
   int m = y.length();
   for (int i = 0; i <= m; i++)
      for (int j = 0; j <= n; j++)
   table[i][j] = 0;
   for (int i = 1; i <= m; i++) {
      for (int j = 1; j <= n; j++) {
         if (x[j - 1] == y[i - 1])
            table[i][j] = 1 + table[i - 1][j - 1];
         else
            table[i][j] = table[i][j - 1];
      }
   }
   int ans = 0;
   for (int i = 1; i <= m; i++)
   ans = max(ans, table[i][n]);
   return ans;
}
int main() {
   string x = "ABCD";
   string y = "BACDBDCD";
   cout << "Length of Maximum subsequence substring is: " << maxSubLength(x, y);
}

ผลลัพธ์

Length of Maximum subsequence substring is: 3