Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để in chuỗi commonsubstring dài nhất.
Đối với điều này, chúng ta sẽ được cung cấp hai chuỗi nói A và B. Chúng ta phải in chuỗi dài nhất chung cho hai chuỗi đầu vào A và B.
Ví dụ:nếu chúng ta được tặng “HelloWorld” và “sách thế giới”. Khi đó, chuỗi con chung dài nhất, trong trường hợp này, sẽ là “thế giới”.
Ví dụ
#include <iostream>
#include <stdlib.h>
#include <string.h>
using namespace std;
void print_lstring(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;
}
}
if (len == 0) {
cout << "There exists no common substring";
return;
}
char* final_str = (char*)malloc((len + 1) * sizeof(char));
while (longest[row][col] != 0) {
final_str[--len] = X[row - 1];
row--;
col--;
}
cout << final_str;
}
int main(){
char X[] = "helloworld";
char Y[] = "worldbook";
int m = strlen(X);
int n = strlen(Y);
print_lstring(X, Y, m, n);
return 0;
} Đầu ra
world