मान लीजिए हमारे पास दो लोअरकेस स्ट्रिंग्स X और Y हैं, हमें उनके सबसे लंबे सामान्य उपस्ट्रिंग की लंबाई ज्ञात करनी है।
उदाहरण के लिए, यदि इनपुट X = "helloworld" और Y = "worldbook" है, तो आउटपुट 5 होगा, क्योंकि "world" सबसे लंबा सामान्य उपस्ट्रिंग है और इसकी लंबाई 5 है।
समाधान दृष्टिकोण
इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:
- आकार (m+1) x (n+1) का एक 2D सरणी
longestपरिभाषित करें। len := 0आरंभ करें।- बाहरी लूप: i = 0 से m तक पुनरावृति करें।
- आंतरिक लूप: j = 0 से n तक पुनरावृति करें।
- यदि i == 0 या j == 0, तो
longest[i][j] := 0सेट करें। - अन्यथा यदि X[i-1] == Y[j-1], तो:
longest[i][j] := longest[i-1][j-1] + 1- यदि
len < longest[i][j], तोlenअपडेट करें और वर्तमान पंक्ति व स्तंभ संग्रहीत करें।
- अन्यथा
longest[i][j] := 0सेट करें। - अंत में
lenवापस करें।
C++ कार्यान्वयन
#include <iostream>
#include <cstring>
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