C++-এ সিকোয়েন্স সেটে লংগেস্ট কমন সাবসিকোয়েন্স (LCS) খুঁজে বের করা

এখানে আমরা একটি সিকোয়েন্স সেটে সবচেয়ে লম্বা কমন সাবসিকোয়েন্স (Longest Common Subsequence) খুঁজে বের করার C++ প্রোগ্রাম দেখব। দ্রষ্টব্য: প্রদত্ত কোড আসলে লংগেস্ট কমন প্রিফিক্স (Longest Common Prefix) খুঁজে বের করে, LCS না।

এলগরিদম

Begin
    স্ট্রিংয়ের অ্যারে ইনপুট নিন।
    function matchedPrefixtill(): স্ট্রিং s1 এবং s2-এর মিলে যাওয়া প্রিফিক্স খুঁজে বের করুন:
        n1 = s1-এর দৈর্ঘ্য।
        n2 = s2-এর দৈর্ঘ্য।
        for i = 0, j = 0 to i <= n1-1 && j <= n2-1
            if s1[i] != s2[j] break
            result.push_back(s1[i])
        return result
End
Begin
    function matchedPrefix(): স্ট্রিং অ্যারে থেকে লংগেস্ট ম্যাচড প্রিফিক্স রিটার্ন করুন:
        for int i = 1 to n-1
            pre = matchedPrefixtill(pre, a[i])
        return pre.
End

উদাহরণ

#include <bits/stdc++.h>
using namespace std;

string matchedPrefixtill(string s1, string s2) {
    string res;
    int n1 = s1.length();
    int n2 = s2.length();
    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