Chương trình tìm độ dài của chuỗi con chung dài nhất trong C ++

Giả sử chúng ta có hai chuỗi chữ thường X và Y, chúng ta phải tìm độ dài của chuỗi con chung dài nhất của chúng.

Vì vậy, nếu đầu vào là X ="helloworld", Y ="worldbook", thì đầu ra sẽ là 5, vì "world" là chuỗi con chung dài nhất và độ dài của nó là 5.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một mảng có kích thước dài nhất:m + 1 x n + 1.

• len:=0

• để khởi tạo i:=0, khi i <=m, cập nhật (tăng i lên 1), thực hiện -

  • để khởi tạo j:=0, khi j <=n, cập nhật (tăng j lên 1), thực hiện -

    • nếu tôi giống 0 hoặc j giống 0, thì -

      • dài nhất [i, j]:=0

    • ngược lại khi X [i - 1] giống với Y [j - 1] thì -

      • lâu nhất [i, j]:=lâu nhất [i - 1, j - 1] + 1

      • if len

        • len:=long [i, j]

        • hàng:=i

        • col:=j

    • Nếu không

      • dài nhất [i, j]:=0

  • return len

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <iostream>
#include <stdlib.h>
#include <string.h>
using namespace std;
int solve(char* X, char* Y, int m, int n){
   int longest[m + 1][n + 1];
   int len = 0;
   int row, col;
   for (int i = 0; i <= m; i++) {
      for (int j = 0; j <= n; j++) {
         if (i == 0 || j == 0)
            longest[i][j] = 0;
         else if (X[i - 1] == Y[j - 1]) {
            longest[i][j] = longest[i - 1][j - 1] + 1;
            if (len < longest[i][j]) {
               len = longest[i][j];
               row = i;
               col = j;
            }
         }
         else
            longest[i][j] = 0;
      }
   }
   return len;
}
int main(){
   char X[] = "helloworld";
   char Y[] = "worldbook";
   int m = strlen(X);
   int n = strlen(Y);
   cout << solve(X, Y, m, n);
   return 0;
}

Đầu vào

"helloworld", "worldbook"

Đầu ra

5