C++-এ সর্বোচ্চ দৈর্ঘ্যের ডুপ্লিকেট সাবস্ট্রিং বের করা

সমস্যা বিবরণ

একটি স্ট্রিং S দেওয়া থাকলে, সেটিতে ২ বা তার বেশি বার হয়েছে এমন সব সংলগ্ন সাবস্ট্রিং বিবেচনা করতে হবে (ওভারল্যাপ হতে পারে)। আমাদের 그중 সর্বোচ্চ দৈর্ঘ্যের ডুপ্লিকেট সাবস্ট্রিংটি খুঁজে বের করতে হবে। যদি এমন কোনো সাবস্ট্রিং না থাকে, তবে খালি স্ট্রিং রিটার্ন করব। উত্তর বড় হতে পারে, তাই 10^9+7 মডুলো দিয়ে রিটার্ন করব।

উদাহরণ

ইনপুট: "ababbaba" → আউটপুট: "bab"

সমাধান পদ্ধতি

• রলিং হ্যাশ (Rolling Hash) ও বাইনারি সার্চ ব্যবহার করা হয়।
• একটি নির্দিষ্ট দৈর্ঘ্য x এর সাবস্ট্রিং ডুপ্লিকেট আছে কিনা যাচাই করার জন্য ok() ফাংশন ব্যবহার করা হয়।
• বাইনারি সার্চ দিয়ে সর্বোচ্চ সম্ভব দৈর্ঘ্য নির্ণয় করা হয়।
• হ্যাশ সংঘর্ষ রোধের জন্য মডুলার=arithmetic ব্যবহার করা হয়।

C++ বাস্তবায়ন

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;

class Solution {
    int m = 1e9 + 7;
    vector<int> power;
    
    int add(lli a, lli b) { return ((a % m) + (b % m)) % m; }
    int sub(lli a, lli b) { return ((a % m) - (b % m) + m) % m; }
    int mul(lli a, lli b) { return ((a % m) * (b % m)) % m; }
    
    string ok(int x, string s) {
        if (x == 0) return "";
        unordered_map<int, vector<int>> hash;
        lli current = 0;
        
        for (int i = 0; i < x; i++)
            current = add(mul(current, 26), s[i] - 'a');
        hash[current] = vector<int>(1, 0);
        
        int n = s.size();
        for (int i = x; i < n; i++) {
            current = sub(current, mul(power[x - 1], s[i - x] - 'a'));
            current = add(mul(current, 26), s[i] - 'a');
            
            if (hash.count(current)) {
                for (auto& it : hash[current]) {
                    if (s.substr(it, x) == s.substr(i - x + 1, x))
                        return s.substr(it, x);
                }
            } else {
                hash[current].push_back(i - x + 1);
            }
        }
        return "";
    }
    
public:
    string longestDupSubstring(string S) {
        string ret = "";
        int n = S.size();
        power = vector<int>(n, 1);
        for (int i = 1; i < n; i++)
            power[i] = mul(power[i - 1], 26);
        
        int low = 0, high = n - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            string temp = ok(mid, S);
            if (temp.empty()) high = mid - 1;
            else {
                if (temp.size() > ret.size()) ret = temp;
                low = mid + 1;
            }
        }
        return ret;
    }
};

int main() {
    Solution ob;
    cout << ob.longestDupSubstring("ababbaba");
    return 0;
}

ইনপুট ও আউটপুট

ইনপুট: "ababbaba"

আউটপুট: "bab"