यहां हम एक C++ प्रोग्राम पर चर्चा करेंगे जो एक सेट ऑफ सीक्वेंस में सभी सीक्वेंस के लिए कॉमन सबसे लंबी सबसीक्वेंस खोजता है।
एल्गोरिदम
Begin
स्ट्रिंग्स की ऐरे को इनपुट के रूप में लें।
function matchedPrefixtill(): स्ट्रिंग s1 और s2 के बीच मैच्ड प्रीफिक्स खोजें:
n1 = स्ट्रिंग s1 की लंबाई स्टोर करें।
n2 = स्ट्रिंग s2 की लंबाई स्टोर करें।
for i = 0, j = 0 से i <= n1 - 1 && j <= n2 - 1 तक
यदि s1[i] != s2[j]
ब्रेक
result.push_back(s1[i])
return result
End
function matchedPrefix(): स्ट्रिंग्स की ऐरे से सबसे लंबा मैच्ड प्रीफिक्स लौटाता है:
for int i = 1 से n - 1 तक
pre = matchedPrefixtill(pre, a[i])
return pre.
End
End
उदाहरण
#include <bits/stdc++.h>
using namespace std;
string matchedPrefixtill(string s1, string s2) {
string res;
int n1 = s1.length(); // स्ट्रिंग s1 की लंबाई स्टोर करें
int n2 = s2.length(); // स्ट्रिंग s2 की लंबाई स्टोर करें
for (int i = 0, j = 0; i <= n1 - 1 && j <= n2 - 1; i++, j++) {
if (s1[i] != s2[j])
break;
res.push_back(s1[i]);
}
return (res);
}
string matchedPrefix(string a[], int n) {
string pre = a[0];
for (int i = 1; i <= n - 1; i++)
pre = matchedPrefixtill(pre, a[i]);
return (pre);
}
int main() {
string a[] = {"Tutorialspoint", "Tutor", "Tutorials"}; // इनपुट लेना
int n = sizeof(a) / sizeof(a[0]);
string res = matchedPrefix(a, n);
if (res.length())
cout << "Longest common subsequence is matched - " << res.c_str();
else
cout << "No matched prefix";
return (0);
}
आउटपुट
Longest common subsequence is matched - Tutor
नोट: यह प्रोग्राम वास्तव में लॉन्गेस्ट कॉमन प्रीफिक्स (LCP) खोजता है, लॉन्गेस्ट कॉमन सबसीक्वेंस (LCS) नहीं। LCS के लिए डायनामिक प्रोग्रामिंग की आवश्यकता होती है (O(n*m) प्रति जोड़ी)। LCP केवल शुरुआत से मेल खाने वाले कैरेक्टर्स की जांच करता है, जबकि LCS कहीं भी मेल खाने वाले कैरेक्टर्स को अनुमति देता है। शीर्षक भ्रामक है - कोड प्रीफिक्स के लिए काम करता है, सबसीक्वेंस के लिए नहीं।