โปรแกรมค้นหาความยาวของสตริงย่อยทั่วไปที่ยาวที่สุดใน C++

สมมติว่าเรามีสตริงตัวพิมพ์เล็ก X และ Y เราต้องหาความยาวของสตริงย่อยร่วมที่ยาวที่สุด

ดังนั้น หากอินพุตเป็นเหมือน X ="helloworld", Y ="worldbook" ผลลัพธ์จะเป็น 5 เนื่องจาก "world" เป็นสตริงย่อยทั่วไปที่ยาวที่สุด และมีความยาวเท่ากับ 5

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดขนาดอาร์เรย์ที่ยาวที่สุด:m+1 x n+1

• เลน :=0

• สำหรับการเริ่มต้น i :=0 เมื่อ i <=m อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • สำหรับการเริ่มต้น j :=0 เมื่อ j <=n อัปเดต (เพิ่ม j โดย 1) ทำ -

    • ถ้าฉันเหมือนกับ 0 หรือ j เหมือนกับ 0 แล้ว −

      • ยาวที่สุด[i, j] :=0

    • มิฉะนั้นเมื่อ X[i - 1] เหมือนกับ Y[j - 1] แล้ว −

      • ยาวที่สุด[i, j] :=ยาวที่สุด[i - 1, j - 1] + 1

      • ถ้าเลน <ยาวที่สุด[i, j] แล้ว −

        • len :=ยาวที่สุด[i, j]

        • แถว :=ผม

        • col :=j

    • มิฉะนั้น

      • ยาวที่สุด[i, j] :=0

  • กลับเลน

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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;
}

อินพุต

"helloworld", "worldbook"

ผลลัพธ์

5