C++에서 가장 긴 공통 부분 문자열의 길이를 찾는 프로그램

<시간/>

두 개의 소문자 문자열 X와 Y가 있다고 가정하고 가장 긴 공통 부분 문자열의 길이를 찾아야 합니다.

따라서 입력이 X ="helloworld", Y ="worldbook"과 같으면 "world"가 가장 긴 공통 부분 문자열이고 길이가 5이므로 출력은 5가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

가장 긴 크기의 배열 정의:m+1 x n+1.
len :=0
초기화 i :=0의 경우, i <=m일 때 업데이트(i를 1만큼 증가), −
- 초기화 j :=0의 경우 j <=n일 때 업데이트(j를 1만큼 증가), −
  - i가 0과 같거나 j가 0과 같으면 -
    - 가장 긴[i, j] :=0
  - 그렇지 않으면 X[i - 1]이 Y[j - 1]과 같을 때 -
    - 가장 긴[i, j] :=가장 긴[i - 1, j - 1] + 1
    - len <가장 긴[i, j]이면 -
      - len :=가장 긴[i,j]
      - 행 :=나는
      - 열 :=j
  - 그렇지 않으면
    - 가장 긴[i, j] :=0
- 반환 len

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#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"