C++-এ টার্গেট স্ট্রিংয়ের সমান ইউনিক সাবসিকোয়েন্সের সংখ্যা বের করা

মান লইয়া আমাদের দুটি লোয়ারকেস স্ট্রিং s এবং t আছে, আমাদের বের করতে হবে s-এর সাবসিকোয়েন্স কতগুলো t-এর সমান। যদি উত্তর বড় হয় তবে 10^9 + 7 দিয়ে মড করুন।

তবে, যদি ইনপুট হয় s = "abbd" t = "bd", তবে আউটপুট হবে 2, কারণ দুটি সম্ভাব্য সাবসিকোয়েন্স "bd"।

s[1] concatenate s[3]
s[2] concatenate s[3].

এটি সমাধান করতে, আমরা এই ধাপগুলো ফলো করব:

m := 10^9 + 7
যদি t-এর সাইজ ০ হয়, ০ রিটার্ন করুন
যদি t == s হয়, ১ রিটার্ন করুন
যদি t-এর সাইজ > s-এর সাইজ হয়, ০ রিটার্ন করুন
t-এর সাইজ + ১ সাইজের একটি table অ্যারে ডিফাইন করুন ০ দিয়ে ফিল্ড
table[0] := 1
i = 0 থেকে s.size()-১ পর্যন্ত:
- onsave := table
- j = 0 থেকে table.size()-১ পর্যন্ত:
  - যদি s[i] == t[j], তবে table[j+1] = (table[j+1] % m + onsave[j] % m) % m
table[t.size()] % m রিটার্ন করুন

বेहतर বোঝার জন্য ইমপ্লিমেন্টেশন দেখুন:

উদাহরণ

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

int solve(string s, string t) {
    int m = 1000000007;
    if (t.size() == 0)
        return 0;
    if (t == s)
        return 1;
    if (t.size() > s.size())
        return 0;
    vector<int> table(t.size() + 1, 0);
    table[0] = 1;
    for (int i = 0; i < s.size(); i++) {
        vector<int> onsave = table;
        for (int j = 0; j < table.size(); j++) {
            if (s[i] == t[j]) {
                table[j + 1] = (table[j + 1] % m + onsave[j] % m) % m;
            }
        }
    }
    return table[t.size()] % m;
}

main(){
    string s = "abbd", t = "bd";
    cout << (solve(s, t));
}

ইনপুট

"abbd", "bd"