C++で最長の一般的な部分文字列の長さを見つけるプログラム

2つの小文字の文字列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と同じ場合、-

      • longest [i、j]：=0

    • それ以外の場合、X[i-1]がY[j-1]と同じである場合、-

      • longest [i、j]：=longest [i-1、j-1] + 1

      • len

        • len：=longest [i、j]

        • 行：=i

        • col：=j

    • それ以外の場合

      • longest [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"

出力

5