मान लीजिए हमारे पास एक स्ट्रिंग S है, उन सभी डुप्लिकेट सन्निहित सबस्ट्रिंग्स पर विचार करें जो 2 या अधिक बार आते हैं। (घटनाएं ओवरलैप हो सकती हैं।) हमें उस डुप्लिकेट सबस्ट्रिंग को ढूंढना है जिसकी लंबाई सबसे अधिक संभव हो। यदि ऐसा कोई सबस्ट्रिंग नहीं है, तो एक खाली स्ट्रिंग वापस करें। चूंकि उत्तर बहुत बड़ा हो सकता है, इसलिए इसे मॉड्यूलो 10^9 + 7 में वापस करें।
उदाहरण के लिए, यदि इनपुट "ababbaba" है, तो आउटपुट "bab" होगा।
हल करने का दृष्टिकोण
इस समस्या को हल करने के लिए हम रोलिंग हैश के साथ बाइनरी सर्च का उपयोग करते हैं:
मॉड्यूलो अंकगणित के लिए सहायक फ़ंक्शन परिभाषित करें (add, sub, mul)
आधार 26 की घातों की सरणी पूर्व-गणना करें
एक फ़ंक्शन ok(x, s) परिभाषित करें जो जांचता है कि क्या लंबाई x का डुप्लिकेट सबस्ट्रिंग मौजूद है
रोलिंग हैश का उपयोग करके सभी लंबाई-x सबस्ट्रिंग्स के हैश मानों की गणना करें
हैश टकराव को संभालने के लिए वास्तविक सबस्ट्रिंग तुलना के साथ सत्यापित करें
मुख्य फ़ंक्शन में, उत्तर की लंबाई पर बाइनरी सर्च करें
उदाहरण
#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, 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;
}
};
int main(){
Solution ob;
cout << (ob.longestDupSubstring("ababbaba"));
return 0;
}
इनपुट
"ababbaba"
आउटपुट
bab