<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 <typename T>
vector<int> prefixDoubling(const T& s) {
    const int n = s.size();
    vector<int> suff_arr(n), rank(n), temp(n);

    for(int i = 0; i < n; ++i)
        suff_arr[i] = i, rank[i] = s[i];
 
    auto countSort = [&](int k) {
        vector<int> count(max(n, 256), 0), new_suff_arr(n);

        // Counting sort based on the second half of the rank pair
        for(int i = 0; i < n; ++i) {
            if(!k) { count[rank[suff_arr[i]]]++; continue; }
            int rank2 = (suff_arr[i] + k < n) ? rank[suff_arr[i] + k] : -1;
            count[rank2 + 1]++;  // +1 to handle -1 ranks
        }
        for(int i = 1; i < count.size(); ++i) 
            count[i] += count[i - 1];
        for(int i = n - 1; i >= 0; --i) {
            if(!k) { new_suff_arr[--count[rank[suff_arr[i]]]] = suff_arr[i]; continue; }
            int rank2 = (suff_arr[i] + k < n) ? rank[suff_arr[i] + k] : -1;
            new_suff_arr[--count[rank2 + 1]] = suff_arr[i];
        }

        swap(suff_arr, new_suff_arr);
    };
 
    for(int k = 1; k < n; k <<= 1){
        auto compare = [&](int a, int b) -> bool {
            if (rank[a] != rank[b]) return rank[a] < rank[b];
            int ra = (a + k < n) ? rank[a + k] : -1;
            int rb = (b + k < n) ? rank[b + k] : -1;
            return ra < rb;
        };

        //Use countSort if string else consider the standard sorting
        countSort(k);
        countSort(0);
        // sort(all(suff_arr), compare);

        temp[suff_arr[0]] = 0;
        for(int i = 1; i < n; ++i)
            temp[suff_arr[i]] = temp[suff_arr[i - 1]] + compare(suff_arr[i - 1], suff_arr[i]);
    
        swap(rank, temp);    
        if(rank[suff_arr[n - 1]] == n - 1) break;
    }
 
    return suff_arr;
}

vector<int> kasai(const string &s, const vector<int> &suffix_arr) {
    int n = s.size();
    vector<int> rank(n), lcp(n, 0);

    for (int i = 0; i < n; ++i)
        rank[suffix_arr[i]] = i;

    int h = 0;
    for (int i = 0; i < n; ++i) {
        if (rank[i] > 0) {
            int j = suffix_arr[rank[i] - 1];
            while (i + h < n && j + h < n && s[i + h] == s[j + h])
                h++;
            lcp[rank[i]] = h;
            if (h > 0)
                h--;
        }
    }

    return lcp;
}

class Solution {
public:
    string longestDupSubstring(string s) {
        const vector<int> suff_arr = prefixDoubling(s);
        const vector<int> lcp = kasai(s, suff_arr);

        int best_len = 0;
        int begin = -1;
        for(int i = 1; i < s.size(); i++)
            if(lcp[i] > best_len)
                best_len = lcp[i], begin = suff_arr[i];

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

// #define MAIN_ACTIVE
#ifdef MAIN_ACTIVE

// #define SOLVING
void solve() {
    string s;
    cin >> s;

    vector<int> suff_arr = prefixDoubling(s);
    print(suff_arr)
}

int main() {

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

    return EXIT_SUCCESS;
}
#endif
48740