<p>Given a string <code>s</code>, consider all <em>duplicated substrings</em>: (contiguous) substrings of s that occur 2 or more times.&nbsp;The occurrences&nbsp;may overlap.</p>

<p>Return <strong>any</strong> duplicated&nbsp;substring that has the longest possible length.&nbsp;If <code>s</code> does not have a duplicated substring, the answer is <code>&quot;&quot;</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> s = "banana"
<strong>Output:</strong> "ana"
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> s = "abcd"
<strong>Output:</strong> ""
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= s.length &lt;= 3 * 10<sup>4</sup></code></li>
	<li><code>s</code> consists of lowercase English letters.</li>
</ul>

#include <bits/stdc++.h> 

// #define MAIN_ACTIVE
// #define IO_FROM_FILE

using namespace std;
#define int64_t wadwafesfesfes21321300242142104210321
using int64_t = long long;
using pii = pair<int,int>;
using pil = pair<int,int64_t>;
using pli = pair<int64_t,int>;
using pll = pair<int64_t,int64_t>;
#define umap unordered_map
#define uset unordered_set
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define emp_back emplace_back
#define bitcount(x) __builtin_popcount((x))
#define mbin(val, cap) bitset<64>(val).to_string().substr(64 - cap)
#define PQ(x, y) priority_queue<x, vector<x>, y<x>>
// #define PQD(x, y) priority_queue<x, vector<x>, decltype(y)>
#define print(x) cout << "[ " << #x << " ]: " << x << "\n";
#define printc(x) cout << "[ " << #x << " ]: [", show(all(x), ", ", false), cout << "]\n";
#define e_ cout << "\n";
template <typename F, typename S> ostream& operator << (ostream& os, const pair<F, S>& duo) { return os << "(" << duo.first << ", " << duo.second << ")"; }
template <typename Iter> void show(Iter begin, Iter end, const char* sep = " ", bool is_end = true) { for(Iter it = begin; it != end; it++) cout << (it != begin ? sep : "") << *it; if(is_end) cout << "\n"; }
template<typename T, typename Cmp = less<T>> void get_unique(vector<T>& arr, Cmp compare = Cmp()){ sort(all(arr), compare); arr.erase(unique(all(arr)), arr.end()); }
mt19937_64 _GEN(chrono::high_resolution_clock::now().time_since_epoch().count());
template <typename T>
T mrand(T begin, T end) {
    if constexpr (is_integral<T>::value){ uniform_int_distribution<T> _UNI_DIST(begin, end); return _UNI_DIST(_GEN); } 
    else if constexpr (is_floating_point<T>::value) { uniform_real_distribution<T> _UNI_DIST(begin, end); return _UNI_DIST(_GEN); }
}
int fastIO = []{ ios_base::sync_with_stdio(false); cin.tie(NULL); return 0; }();
//0down, 1right, 2up, 3left, 4upleft, 5downright, 6upright, 7downleft, 8stay
constexpr int dx[9] = {0, 1, 0, -1, -1, 1, 1, -1, 0};
constexpr int dy[9] = {1, 0, -1, 0, -1, 1, -1, 1, 0};

template <uint64_t mod = 1'000'000'007>
struct Mint {
    uint64_t val;
    Mint() : val(0) {}
    Mint(int64_t _val) {
        _val %= mod;
        if (_val < 0) _val += mod;
        val = _val;
    }
    Mint& operator += (const Mint& other){ val += other.val; if(val >= mod) val -= mod; return *this; }
    Mint& operator -= (const Mint& other){ val += mod - other.val; if(val >= mod) val -= mod; return *this; }
    Mint& operator *= (const Mint& other){ val = (uint64_t)val * other.val % mod; return *this; }
    Mint& operator /= (const Mint& other){ return *this *= other.inv(); }
    Mint operator + (const Mint& other) const { return Mint(*this) += other; }
    Mint operator - (const Mint& other) const { return Mint(*this) -= other; }
    Mint operator * (const Mint& other) const { return Mint(*this) *= other; }
    Mint operator / (const Mint& other) const { return Mint(*this) /= other; }
    Mint pwr(int64_t expo) const {
        Mint res = 1;
        Mint cur = *this;
        while(expo){
            if(expo & 1) res *= cur;
            cur *= cur; expo >>= 1;
        }
        return res;
    }
    Mint inv() const { return pwr(mod - 2); }
    friend ostream& operator << (ostream& os, const Mint& m) { os << m.val; return os; }
    bool operator == (const Mint& other) const { return val == other.val; }
};

constexpr uint64_t MODS[] = {
    1'000'000'007ull,       // 1e9 + 7
    1'000'000'009ull,       // 1e9 + 9
    1'000'000'003ull,       // 1e9 + 3
    1'000'000'019ull,       // 1e9 + 19
    1'000'000'037ull,       // 1e9 + 37
    1'000'000'061ull,       // 1e9 + 61
    1'000'000'077ull,       // 1e9 + 77
    1'000'000'123ull,       // 1e9 + 123
    1'000'000'007'373ull,   // 1e12 + 373
    1'000'000'007'877ull,   // 1e12 + 877
    1'000'000'009'013ull,   // 1e12 + 9'013
    1'000'000'012'269ull,   // 1e12 + 12'269
    1'000'000'012'773ull,   // 1e12 + 12'773
    1'000'000'016'281ull,   // 1e12 + 16'281
    1'000'000'018'401ull,   // 1e12 + 18'401
    1'000'000'020'157ull,   // 1e12 + 20'157
    1'000'000'022'513ull,   // 1e12 + 22'513
};
using mint1 = Mint<MODS[0]>; 
using mint2 = Mint<MODS[1]>;

class Solution {
public:
    string longestDupSubstring(string s) {
        const int n = s.size();
        const int PRIME = 31;

        auto make_id = [](char ch) -> int {
            return ch - 'a' + 1;
        };

        auto calc = [&](int gap) -> int {
            const mint1 power1 = mint1(PRIME).pwr(gap - 1);
            const mint2 power2 = mint2(PRIME).pwr(gap - 1);

            map<pll, int> got;
            mint1 code1 = 0;
            mint2 code2 = 0;
            for(int right = 0; right < n; right++){
                const int left = right - gap;
                if(left >= 0){
                    code1 -= power1 * make_id(s[left]);
                    code2 -= power2 * make_id(s[left]);
                } 

                code1 = (code1 * PRIME) + make_id(s[right]);
                code2 = (code2 * PRIME) + make_id(s[right]);

                if(left < -1)
                    continue;

                pll code_pair = make_pair(code1.val, code2.val);
                if(got.count(code_pair))
                    return got[code_pair];
                got[code_pair] = left + 1;
            }

            return -1;
        };

        int left = 1;
        int right = n;
        int begin = -1, best = 0;
        while(left <= right){
            const int mid = left + (right - left) / 2;
            const int got = calc(mid);
            if(got != -1)
                begin = got, best = mid, left = mid + 1;
            else
                right = mid - 1;
        }

        return (best) ? s.substr(begin, best) : "";
    }
};

#ifdef MAIN_ACTIVE

void solve() {

#ifdef IO_FROM_FILE
    fout.close();
    fout.open(FILE_NAME + ".out", ios::app);
#endif
    
}

int main() {

    int test_count = 1;
    // cin >> test_count;
    while(test_count--)
        solve();

    return EXIT_SUCCESS;
}
#endif
325220