程序查找C ++中最长的公共子字符串的长度

假设我们有两个小写的字符串X和Y，我们必须找到它们最长的公共子字符串的长度。

因此，如果输入类似于X =“ helloworld”，Y =“ worldbook”，则输出将为5，因为“ world”是最长的公共子字符串，其长度为5。

为了解决这个问题，我们将遵循以下步骤-

• 定义最长的数组：m + 1 x n + 1。

• len：= 0

• 对于初始化i：= 0，当i <= m时，更新（将i增加1），执行-

• 如果i等于0或j等于0，则-

• 否则，当X [i-1]与Y [j-1]相同时，则-

• 除此以外

• 最长[i，j]：= 0

• len：=最长[i，j]

• 行：=我

• col：= j

• longest [i，j]：=最长[i-1，j-1] + 1

• 如果len <longest [i，j]，则-

• 最长[i，j]：= 0

• 对于初始化j：= 0，当j <= n时，更新（将j增加1），执行-

• 返回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