C++ में सबसे लंबा डुप्लीकेट सबस्ट्रिंग

मान लीजिए कि हमारे पास एक स्ट्रिंग एस है, सभी डुप्लिकेट किए गए सन्निहित सबस्ट्रिंग पर विचार करें जो 2 या अधिक बार होते हैं। (घटनाएं ओवरलैप हो सकती हैं।), हमें डुप्लीकेट सबस्ट्रिंग को ढूंढना होगा जिसमें सबसे लंबी संभव लंबाई हो। यदि ऐसा कोई सबस्ट्रिंग नहीं है, तो एक रिक्त स्ट्रिंग लौटाएं। चूंकि उत्तर बहुत बड़ा हो सकता है, इसलिए मॉड 10^9 + 7 में वापस आएं।

इसलिए, यदि इनपुट "अब्बाबा" जैसा है, तो आउटपुट "बाब" होगा

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• मी :=1e9 + 7

• फ़ंक्शन ऐड () को परिभाषित करें, इसमें a, b,

  . लगेगा

• वापसी ((एक मॉड एम) + (बी मॉड एम)) मॉड एम

• एक फ़ंक्शन उप () को परिभाषित करें, इसमें a, b,

  . लगेगा

• वापसी ((एक मॉड एम) - (बी मॉड एम) + एम) मॉड एम

• फ़ंक्शन mul() को परिभाषित करें, इसमें a, b,

  . लगेगा

• वापसी ((एक मॉड एम) * (बी मॉड एम)) मॉड एम

• सरणी शक्ति को परिभाषित करें

• फ़ंक्शन को परिभाषित करें ठीक (), इसमें x, s,

  लगेगा

• यदि x, 0 के समान है, तो -

  • खाली स्ट्रिंग लौटाएं

• हैश नामक एक मानचित्र परिभाषित करें

• वर्तमान:=0

• इनिशियलाइज़ करने के लिए i:=0, जब i

  • वर्तमान:=जोड़ें (मूल (वर्तमान, 26), एस [i] - 'ए')

• हैश [वर्तमान]:=एक सरणी परिभाषित करें (1, 0)

• n :=s का आकार

• इनिशियलाइज़ i :=x के लिए, जब i

  • वर्तमान:=उप (वर्तमान, mul (शक्ति [x - 1], s [i - x] - 'a'))

  • वर्तमान:=जोड़ें (मूल (वर्तमान, 26), एस [i] - 'ए')

  • अगर गिनती हैश का सदस्य है, तो -

    • हैश [वर्तमान] -

      . में यह सब करने के लिए

      • यदि इसमें से x - 1 में s का सबस्ट्रिंग i - x + 1 से x-1 में s के प्रतिस्थापन के समान है, तो -

        • s से x - 1 पर सबस्ट्रिंग लौटाएं

  • अन्यथा

    • हैश के अंत में i - x + 1 डालें [वर्तमान]

• खाली स्ट्रिंग लौटाएं

• मुख्य विधि से, निम्न कार्य करें -

• रिट:=खाली स्ट्रिंग

• n :=S का आकार

• शक्ति :=आकार n की एक सरणी परिभाषित करें और इसे 1

  . से भरें

• इनिशियलाइज़ करने के लिए मैं :=1, जब i

  • शक्ति[i] :=mul(शक्ति[i - 1], 26)

• निम्न :=0, उच्च :=n - 1

• जबकि कम <=उच्च, करें −

  • मध्य :=निम्न + (उच्च-निम्न) /2

  • अस्थायी:=ठीक (मध्य, एस)

  • यदि अस्थायी का आकार 0 के समान है, तो -

    • उच्च :=मध्य - 1

  • अन्यथा

    • यदि अस्थायी का आकार> रिट का आकार, तो -

      • रिट:=अस्थायी

    • कम :=मध्य + 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