<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 DEBUG_ON
#define TERRORIST

#ifdef TERRORIST
using namespace std;
const uint64_t SEED_RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
// #define TYPE_IT(It) typename iterator_traits<It>::value_type
#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 PI 3.14159265358979323846
#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)
#ifdef DEBUG_ON
    #define print(x) cout << "[ " << #x << " ]: " << x << "\n";
    #define e_ cout << "\n";
#else
    #define print(x)
    #define e_
#endif
template<typename F, typename S> ostream& operator << (ostream &cout, pair<F, S> const &p) { return cout << "(" << p.first << ", " << p.second << ")"; }
template<typename T> ostream& operator << (ostream &cout, vector<T> const &v) { cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";}
template <typename K, typename V> ostream& operator << (ostream& cout, const map<K, V>& omp) {for(auto& [k, v] : omp) { cout << "(" << k << ": " << v << ")"; if(&v != &omp.rbegin()->second) cout << ", ";} return cout;}
template<typename T> ostream& operator << (ostream& cout, const set<T>& ost) {cout << "{"; for(auto& v : ost) { cout << v; if(v != *ost.rbegin()) cout << ", "; } return cout << "}";}
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(SEED_RANDOM);
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};
#endif

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; }
};

const uint64_t MOD = 1e12+39; // 1e9 + 7 // 1e12+39 // 769'660'252'576'9ull
using mint = Mint<MOD>; 
const int nax = 3'000'0;
const int PRIME = 29;
mint power[nax];
int init = []{
    power[0] = 1;
    for(int i = 1; i < nax; i++)
        power[i] = power[i - 1] * PRIME;
    return 0;
}();

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

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

        auto calc = [&](int len) -> pii {
            uset<uint64_t> st;
            mint code = 0;
            for(int i = 0; i < n; i++){
                const int j = i - len;
                if(j >= 0)
                    code -= power[len - 1] * makeId(s[j]);
                code = code * PRIME + makeId(s[i]);
                if(j < -1) continue;
                if(st.count(code.val))
                    return make_pair(j + 1, len);
                st.insert(code.val);
            }

            return make_pair(-1, -1);
        };

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

        return (best.first != -1) ? s.substr(best.first, best.second) : "";
    }
};

// #define MAIN_ACTIVE
#ifdef MAIN_ACTIVE

// #define SOLVING
void solve() {

}

int main() {

    #ifdef SOLVING
        int test_case;
        cin >> test_case;
        while(test_case--)
            solve();
    #else
        solve();
    #endif

    return EXIT_SUCCESS;
}
#endif
210020