C++ এ দীর্ঘতম ডুপ্লিকেট সাবস্ট্রিং

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

সুতরাং, ইনপুট যদি "ababbaba" এর মত হয়, তাহলে আউটপুট হবে "bab"

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• m :=1e9 + 7

• একটি ফাংশন add() সংজ্ঞায়িত করুন, এটি a, b,

  লাগবে

• ফিরুন ((a mod m) + (b mod m)) mod m

• একটি ফাংশন সাব() সংজ্ঞায়িত করুন, এটি a, b,

  লাগবে

• ফিরুন ((a mod m) - (b mod m) + m) mod m

• একটি ফাংশন mul() সংজ্ঞায়িত করুন, এটি a, b,

  লাগবে

• (a mod m) * (b mod m)) mod m

  ফেরত দিন

• একটি অ্যারে পাওয়ার সংজ্ঞায়িত করুন

• একটি ফাংশন সংজ্ঞায়িত করুন ok(), এটি x, s,

  লাগবে

• যদি x 0 এর সমান হয়, তাহলে −

  • খালি স্ট্রিং ফেরত দিন

• হ্যাশ

  নামে একটি মানচিত্র সংজ্ঞায়িত করুন

• বর্তমান :=0

• আরম্ভ করার জন্য i :=0, যখন i

  • বর্তমান :=add(mul(current, 26), s[i] - 'a')

• হ্যাশ[বর্তমান] :=একটি অ্যারে সংজ্ঞায়িত করুন (1, 0)

• n :=s

  এর আকার

• আরম্ভ করার জন্য i :=x, যখন i

  • বর্তমান :=উপ(কারেন্ট, mul(power[x - 1], s[i - x] - 'a'))

  • বর্তমান :=add(mul(current, 26), s[i] - 'a')

  • যদি গণনা হ্যাশের সদস্য হয়, তাহলে -

    • হ্যাশ [বর্তমান] -

      -এ সব কিছুর জন্য

      • যদি s থেকে x - 1 এর সাবস্ট্রিং i - x + 1 থেকে x- 1 থেকে s-এর সাবস্ট্রিংয়ের সমান হয়, তাহলে −

        • এটি থেকে s এর সাবস্ট্রিং x - 1

          এ ফেরত দিন

  • অন্যথায়

    • হ্যাশ[বর্তমান]

      এর শেষে i - x + 1 ঢোকান

• খালি স্ট্রিং ফেরত দিন

• প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -

• ret :=খালি স্ট্রিং

• n :=S

  এর আকার

• power :=n আকারের একটি অ্যারে নির্ধারণ করুন এবং এটি 1

  দিয়ে পূরণ করুন

• আরম্ভ করার জন্য i :=1, যখন i

  • power[i] :=mul(power[i - 1], 26)

• নিম্ন :=0, উচ্চ :=n - 1

• যখন কম <=উচ্চ, করুন −

  • মধ্য :=নিম্ন + (উচ্চ - নিম্ন) /2

  • temp :=ঠিক আছে(মিড, এস)

  • যদি তাপমাত্রার আকার 0 এর মতো হয়, তাহলে −

    • উচ্চ :=মধ্য - 1

  • অন্যথায়

    • যদি টেম্পের সাইজ> রেটের সাইজ হয়, তাহলে −

      • ret :=temp

    • নিম্ন :=মধ্য + 1

• রিটার্ন রিটার্ন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
   public:
   int m = 1e9 + 7;
   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;
   }
   vector<int> power;
   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 "";
   }
   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;
      int high = n - 1;
      while (low <= high) {
         int mid = low + (high - low) / 2;
         string temp = ok(mid, S);
         if (temp.size() == 0) {
            high = mid - 1;
         } else {
            if (temp.size() > ret.size())
            ret = temp;
            low = mid + 1;
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.longestDupSubstring("ababbaba"));
}

ইনপুট

"ababbaba"

আউটপুট

bab