এই টিউটোরিয়ালে সবচেয়ে লম্বা কমন সাবস্ট্রিং (longest common substring) প্রিন্ট করার প্রোগ্রাম আলোচনা করা হবে।
দুটি স্ট্রিং A এবং B দেওয়া থাকলে, দুটো স্ট্রিংয়ের কমন সবচেয়ে লম্বা সাবস্ট্রিং প্রিন্ট করতে হবে। উদাহরণস্বরূপ, "HelloWorld" এবং "world book" দেওয়া থাকলে, কমন সাবস্ট্রিং "world"।
উদাহরণ
#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; } আউটপুট
world
