peMf4n - Online C++0x Compiler & Debugging Tool

// Compact Suffix-Array-oriented template with 30 small helper functions.
// Each helper is standalone (outside the class) so you can remove what you don't need.
// All helper functions include a short "command" comment: what it does, inputs, outputs, complexity.
// Build: C++17

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct SuffixArray {
    // Build SA + LCP + RMQ over LCP.
    // Input: original string (no sentinel). Constructor adds sentinel internally.
    string s; // with sentinel at the end
    int n;    // length including sentinel
    vector<int> sa;   // sa[i] = starting index of i-th suffix in sorted order
    vector<int> rank_; // rank_[pos] = index in sa
    vector<int> lcp;  // lcp[i] = LCP(sa[i], sa[i-1]) (lcp[0]=0)
    int LOG;
    vector<vector<int>> st; // sparse table over lcp

    explicit SuffixArray(const string &orig = "") {
        if (orig.size()) build(orig);
    }

    void build(const string &orig) {
        s = orig;
        s.push_back('$'); // sentinel
        n = (int)s.size();
        sa.assign(n, 0);
        rank_.assign(n, 0);
        lcp.assign(n, 0);

        // SA build (O(n log n))
        vector<pair<char,int>> a(n);
        for (int i = 0; i < n; ++i) a[i] = {s[i], i};
        sort(a.begin(), a.end());
        for (int i = 0; i < n; ++i) sa[i] = a[i].second;
        vector<int> c(n);
        c[sa[0]] = 0;
        for (int i = 1; i < n; ++i)
            c[sa[i]] = c[sa[i-1]] + (a[i].first != a[i-1].first);

        int k = 0;
        vector<int> pn(n), cn(n);
        while ((1<<k) < n) {
            for (int i = 0; i < n; ++i)
                pn[i] = (sa[i] - (1<<k) + n) % n;
            // counting sort by class c
            vector<int> cnt(n);
            for (int i = 0; i < n; ++i) cnt[c[i]]++;
            vector<int> pos(n);
            for (int i = 1; i < n; ++i) pos[i] = pos[i-1] + cnt[i-1];
            for (int x : pn) sa[pos[c[x]]++] = x;
            cn[sa[0]] = 0;
            for (int i = 1; i < n; ++i) {
                pair<int,int> prev = {c[sa[i-1]], c[(sa[i-1] + (1<<k)) % n]};
                pair<int,int> now  = {c[sa[i]],     c[(sa[i]     + (1<<k)) % n]};
                cn[sa[i]] = cn[sa[i-1]] + (now != prev);
            }
            c = cn;
            ++k;
            if (c[sa.back()] == n-1) break;
        }
        for (int i = 0; i < n; ++i) rank_[sa[i]] = i;

        // Kasai LCP (O(n))
        int h = 0;
        for (int i = 0; i < n; ++i) {
            int r = rank_[i];
            if (r == 0) { lcp[r] = 0; continue; }
            int j = sa[r-1];
            while (i+h < n && j+h < n && s[i+h] == s[j+h]) ++h;
            lcp[r] = h;
            if (h) --h;
        }

        // build RMQ on lcp
        LOG = 1;
        while ((1<<LOG) <= n) ++LOG;
        st.assign(n, vector<int>(LOG, INT_MAX));
        for (int i = 0; i < n; ++i) st[i][0] = lcp[i];
        for (int j = 1; j < LOG; ++j)
            for (int i = 0; i + (1<<j) <= n; ++i)
                st[i][j] = min(st[i][j-1], st[i + (1<<(j-1))][j-1]);
    }

    // RMQ on lcp by SA indices range [L+1..R] minimum (L < R)
    int lcp_rmq_by_sa_index(int L, int R) const {
        if (L > R) return 0;
        if (L == R) return lcp[L];
        int l = L+1, r = R;
        if (l > r) return 0;
        int len = r - l + 1;
        int k = 31 - __builtin_clz(len);
        return min(st[l][k], st[r - (1<<k) + 1][k]);
    }

    // LCP between suffixes starting at positions i and j (0-based in original string)
    int lcp_between_positions(int i, int j) const {
        if (i == j) return (n - 1) - i;
        int ri = rank_[i], rj = rank_[j];
        if (ri > rj) swap(ri, rj);
        return lcp_rmq_by_sa_index(ri, rj);
    }

    // helpers to expose
    const vector<int>& get_sa() const { return sa; }
    const vector<int>& get_lcp() const { return lcp; }
    int rank_of(int pos) const { return rank_[pos]; }
    const string& str_with_sentinel() const { return s; }
};

// ---------------------- Helpers / "commands" (30) ----------------------

// 1) Pattern matching (exact search)
// Command: sa_contains(sa, pattern)
// Input: SuffixArray sa, pattern string
// Output: bool true if pattern exists
// Complexity: O(|P| log n)
bool sa_contains(const SuffixArray &sa, const string &pattern) {
    const string &S = sa.str_with_sentinel();
    int n = (int)sa.get_sa().size();
    int L = 0, R = n-1;
    while (L <= R) {
        int mid = (L+R)>>1;
        int pos = sa.get_sa()[mid];
        int cmp = S.compare(pos, pattern.size(), pattern);
        if (cmp == 0) return true;
        if (cmp < 0) L = mid + 1;
        else R = mid - 1;
    }
    return false;
}

// 2) LCP between two suffix starts (by position)
// Command: sa_lcp_between(sa, i, j)
// Input: SA, positions i,j (0-based original)
// Output: int LCP length
// Complexity: O(1) with RMQ
int sa_lcp_between(const SuffixArray &sa, int i, int j) {
    return sa.lcp_between_positions(i, j);
}

// 3) Longest repeated substring
// Command: sa_longest_repeated(sa)
// Input: SA
// Output: longest repeated substring (may be empty)
// Complexity: O(n)
string sa_longest_repeated(const SuffixArray &sa) {
    const auto &lcp = sa.get_lcp();
    const auto &saarr = sa.get_sa();
    int idx = max_element(lcp.begin(), lcp.end()) - lcp.begin();
    if (lcp[idx] == 0) return string();
    const string &S = sa.str_with_sentinel();
    return S.substr(saarr[idx], lcp[idx]);
}

// 4) Longest substring that appears >= k times
// Command: sa_longest_at_least_k(sa, k)
// Input: SA, integer k >= 2
// Output: substring (empty if none)
// Complexity: O(n) with RMQ
string sa_longest_at_least_k(const SuffixArray &sa, int k) {
    if (k <= 1) return ""; // every substring appears >=1 times
    int nsa = (int)sa.get_sa().size();
    int best = 0, best_pos = -1;
    for (int i = 0; i + k - 1 < nsa; ++i) {
        int cur = sa.lcp_rmq_by_sa_index(i, i + k - 1);
        if (cur > best) { best = cur; best_pos = sa.get_sa()[i+1]; }
    }
    if (best == 0) return string();
    const string &S = sa.str_with_sentinel();
    return S.substr(best_pos, best);
}

// 5) Longest palindromic substring (Manacher)
// Command: longest_palindrome(s)
// Input: string s
// Output: longest palindromic substring
// Complexity: O(n)
string longest_palindrome(const string &s) {
    int n = s.size();
    if (n == 0) return "";
    // odd-length centers
    vector<int> d1(n);
    int l=0, r=-1;
    for (int i=0;i<n;i++){
        int k = (i>r)?1:min(d1[l + r - i], r - i + 1);
        while (0<=i-k && i+k<n && s[i-k]==s[i+k]) ++k;
        d1[i]=k--;
        if (i + k > r) { l = i - k; r = i + k; }
    }
    vector<int> d2(n); l=0; r=-1;
    for (int i=0;i<n;i++){
        int k = (i>r)?0:min(d2[l + r - i + 1], r - i + 1);
        while (0<=i-k-1 && i+k<n && s[i-k-1]==s[i+k]) ++k;
        d2[i]=k--;
        if (i + k > r) { l = i - k - 1; r = i + k; }
    }
    int best_len = 0, pos = 0;
    for (int i=0;i<n;i++){
        int len = d1[i]*2-1;
        if (len > best_len) { best_len = len; pos = i - d1[i] + 1; }
        len = d2[i]*2;
        if (len > best_len) { best_len = len; pos = i - d2[i]; }
    }
    return s.substr(pos, best_len);
}

// 6) Longest common substring of two strings (via SA static helper)
// Command: sa_lcs_two(a,b)
// Input: two strings
// Output: LCS string
// Complexity: O(n log n) from SA build
string sa_lcs_two(const string &a, const string &b) {
    // use unique small separators (chars 1 and 2)
    string sep1(1, char(1));
    string sep2(1, char(2));
    string comb = a + sep1 + b + sep2;
    SuffixArray sa(comb);
    int na = (int)a.size();
    int best = 0, pos = 0;
    const auto &saarr = sa.get_sa();
    const auto &lcp = sa.get_lcp();
    for (int i = 1; i < (int)saarr.size(); ++i) {
        int x = saarr[i], y = saarr[i-1];
        bool inA_x = x < na;
        bool inA_y = y < na;
        if (inA_x != inA_y) {
            if (lcp[i] > best) {
                best = lcp[i];
                pos = saarr[i];
            }
        }
    }
    if (best == 0) return string();
    return comb.substr(pos, best);
}

// 7) Longest common substring of K strings (concatenate + sliding window)
// Command: sa_lcs_k(vector<string> strs)
// Input: vector<string> (K)
// Output: longest substring common to all K
// Complexity: O(total_length * log total_length)
string sa_lcs_k(const vector<string> &strs) {
    int k = (int)strs.size();
    if (k == 0) return "";
    // assign separators chars 1..K (must not appear in inputs)
    string comb;
    vector<int> owner; // owner index for each position in comb
    for (int i = 0; i < k; ++i) {
        comb += strs[i];
        comb.push_back(char(1 + i)); // unique separator
    }
    SuffixArray sa(comb);
    int nsa = (int)sa.get_sa().size();
    vector<int> pos_owner(nsa);
    // map sa entry to owner group
    int idx = 0;
    vector<int> start_pos_owner((int)comb.size());
    // build owner by scanning original concatenation: for each position, determine which string it belonged to
    owner.assign((int)comb.size(), -1);
    int cur = 0;
    for (int i = 0; i < k; ++i) {
        for (char ch : strs[i]) {
            owner[cur++] = i;
        }
        owner[cur++] = -1; // separator
    }
    for (int i = 0; i < nsa; ++i) {
        int p = sa.get_sa()[i];
        pos_owner[i] = (p < (int)owner.size()) ? owner[p] : -1;
    }
    // sliding window on SA array to cover all k groups, keep min LCP in window
    vector<int> cnt(k, 0);
    int have = 0;
    int l = 0;
    int best = 0, bestpos = -1;
    for (int r = 0; r < nsa; ++r) {
        int o = pos_owner[r];
        if (o >= 0) { if (cnt[o]++ == 0) ++have; }
        while (have == k && l <= r) {
            // compute min LCP in [l..r] (meaning min of lcp[l+1..r])
            if (l < r) {
                int curmin = sa.lcp_rmq_by_sa_index(l, r);
                if (curmin > best) { best = curmin; bestpos = sa.get_sa()[l+1]; }
            }
            int ol = pos_owner[l];
            if (ol >= 0) { if (--cnt[ol] == 0) --have; }
            ++l;
        }
    }
    if (best == 0) return string();
    return comb.substr(bestpos, best);
}

// 8) Count distinct substrings
// Command: sa_count_distinct(sa)
// Input: SA
// Output: number of distinct substrings (ll)
// Complexity: O(n)
ll sa_count_distinct(const SuffixArray &sa) {
    ll ans = 0;
    const auto &saarr = sa.get_sa();
    const auto &lcp = sa.get_lcp();
    const string &S = sa.str_with_sentinel();
    int n = (int)saarr.size();
    for (int i = 1; i < n; ++i) {
        ll suf_len = (n - 1) - saarr[i];
        ans += max(0LL, suf_len - (ll)lcp[i]);
    }
    return ans;
}

// 9) k-th lexicographic substring
// Command: sa_kth_substring(sa, k)  (1-based k)
// Input: SA, k
// Output: substring or empty if none
// Complexity: O(n)
string sa_kth_substring(const SuffixArray &sa, ll k) {
    const auto &saarr = sa.get_sa();
    const auto &lcp = sa.get_lcp();
    const string &S = sa.str_with_sentinel();
    int n = (int)saarr.size();
    for (int i = 1; i < n; ++i) {
        ll suf_len = (n - 1) - saarr[i];
        ll newsubs = max(0LL, suf_len - (ll)lcp[i]);
        if (k > newsubs) k -= newsubs;
        else {
            ll take = lcp[i] + k;
            return S.substr(saarr[i], (size_t)take);
        }
    }
    return string();
}

// 10) Occurrences count of all distinct substrings (small strings only)
// Command: occurrences_all_small(s)
// Input: original string s (recommend n<=2000)
// Output: vector of (substring, count)
// Complexity: O(n^2 log n) memory/time heavy for big n
vector<pair<string,int>> occurrences_all_small(const string &s) {
    int n = (int)s.size();
    if (n > 2000) return {}; // avoid explosion; caller may prune
    unordered_map<string,int> cnt;
    for (int i = 0; i < n; ++i)
        for (int len = 1; len <= n - i; ++len)
            ++cnt[s.substr(i,len)];
    vector<pair<string,int>> out;
    out.reserve(cnt.size());
    for (auto &kv : cnt) out.emplace_back(kv.first, kv.second);
    sort(out.begin(), out.end());
    return out;
}

// 11) Compare two substrings lexicographically in O(1)
// Command: compare_substrings(sa, l1, r1, l2, r2)
// Input: SA, inclusive indices l1..r1 and l2..r2 (0-based original string)
// Output: -1 if S[l1..r1] < S[l2..r2], 0 if equal, 1 if greater
// Complexity: O(1)
int compare_substrings(const SuffixArray &sa, int l1, int r1, int l2, int r2) {
    int len1 = r1 - l1 + 1, len2 = r2 - l2 + 1;
    int L = sa.lcp_between_positions(l1, l2);
    if (L >= min(len1, len2)) {
        if (len1 == len2) return 0;
        return (len1 < len2) ? -1 : 1;
    }
    char a = sa.str_with_sentinel()[l1 + L];
    char b = sa.str_with_sentinel()[l2 + L];
    return (a < b) ? -1 : 1;
}

// 12) Longest Previous Factor (LPF) naive for small n
// Command: compute_lpf_naive(s)
// Input: string s
// Output: vector<int> LPF where LPF[i] = length of longest substring starting at i that appears earlier
// Complexity: O(n^2) naive
vector<int> compute_lpf_naive(const string &s) {
    int n = (int)s.size();
    vector<int> lpf(n, 0);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            int k = 0;
            while (i + k < n && s[j + k] == s[i + k]) ++k;
            lpf[i] = max(lpf[i], k);
        }
    }
    return lpf;
}

// 13) LZ77 naive factorization (triples (pos,len,nextchar))
// Command: lz77_naive(s)
// Input: s
// Output: vector of tuples (pos,len,nextchar) where pos=previous-match position or 0
// Complexity: O(n^2)
struct LZ77Token { int pos, len; char next; };
vector<LZ77Token> lz77_naive(const string &s) {
    int n = (int)s.size();
    vector<LZ77Token> out;
    for (int i = 0; i < n; ) {
        int best_pos = 0, best_len = 0;
        for (int j = 0; j < i; ++j) {
            int k = 0;
            while (i + k < n && s[j + k] == s[i + k]) ++k;
            if (k > best_len) { best_len = k; best_pos = j; }
        }
        char nextch = (i + best_len < n) ? s[i + best_len] : 0;
        out.push_back({best_pos, best_len, nextch});
        i += max(1, best_len + (nextch ? 1 : 0));
    }
    return out;
}

// 14) Burrows-Wheeler Transform (BWT)
// Command: build_bwt(sa)
// Input: SA built on string with sentinel
// Output: BWT string (length n)
string build_bwt(const SuffixArray &sa) {
    const auto &saarr = sa.get_sa();
    const string &S = sa.str_with_sentinel();
    int n = (int)saarr.size();
    string bwt; bwt.resize(n);
    for (int i = 0; i < n; ++i) {
        int p = saarr[i];
        int idx = (p - 1 + n) % n;
        bwt[i] = S[idx];
    }
    return bwt;
}

// 15) Lightweight FM-index build + backward_search (counts)
// Command: build_fm_index(sa) then fm_count(pattern)
// Input: SA
// Output: FMIndex object and count method
// Complexity: build O(n * alphabet), query O(|P|)
struct FMIndex {
    string bwt;
    map<char,int> C; // total chars < c in lexicographical order
    unordered_map<char, vector<int>> occ; // occ[c][i] = occurrences of c in bwt[0..i-1]
    vector<char> alphabet;
    FMIndex() = default;
    explicit FMIndex(const SuffixArray &sa) {
        bwt = build_bwt(sa);
        int n = (int)bwt.size();
        map<char,int> freq;
        for (char ch : bwt) ++freq[ch];
        int sum = 0;
        for (auto &kv : freq) {
            C[kv.first] = sum;
            alphabet.push_back(kv.first);
            sum += kv.second;
        }
        for (char ch : alphabet) {
            occ[ch].assign(n+1, 0);
        }
        for (int i = 0; i < n; ++i) {
            for (char ch : alphabet) occ[ch][i+1] = occ[ch][i];
            occ[bwt[i]][i+1]++;
        }
    }
    // backward search returns [L,R] in SA (inclusive) or empty pair if none
    pair<int,int> backward_search(const string &pat) const {
        int n = (int)bwt.size();
        int L = 0, R = n - 1;
        for (int i = (int)pat.size()-1; i >= 0; --i) {
            char c = pat[i];
            if (C.find(c) == C.end()) return {-1,-1};
            int cStart = C.at(c);
            int occL = occ.at(c)[L];
            int occR = occ.at(c)[R+1];
            if (occR - occL == 0) return {-1,-1};
            L = cStart + occL;
            R = cStart + occR - 1;
        }
        return {L,R};
    }
    ll count(const string &pat) const {
        auto pr = backward_search(pat);
        if (pr.first == -1) return 0;
        return (ll)pr.second - pr.first + 1;
    }
};

// 16) Minimal rotation (Booth)
// Command: minimal_rotation(s)
// Input: string s
// Output: index of lexicographically minimal rotation (0-based), and rotation string
// Complexity: O(n)
int minimal_rotation_index(const string &s) {
    string ss = s + s;
    int n = s.size();
    int i = 0, j = 1, k = 0;
    while (i < n && j < n && k < n) {
        if (ss[i+k] == ss[j+k]) ++k;
        else if (ss[i+k] > ss[j+k]) { i = i + k + 1; if (i <= j) i = j+1; k = 0; }
        else { j = j + k + 1; if (j <= i) j = i+1; k = 0; }
    }
    return min(i, j);
}
string minimal_rotation(const string &s) {
    int idx = minimal_rotation_index(s);
    string r = s.substr(idx) + s.substr(0, idx);
    return r;
}

// 17) FM-index multi-search wrapper
// Command: fm_multi_search(fm, pattern)
// Input: FMIndex, pattern
// Output: count of occurrences
ll fm_multi_search(const FMIndex &fm, const string &pat) {
    return fm.count(pat);
}

// 18) Nearest lexicographic neighbors for a pattern
// Command: nearest_lex_neighbors(sa, pattern)
// Input: SA, pattern
// Output: pair(prev_suffix_pos, next_suffix_pos) (-1 if none)
// Complexity: O(log n)
pair<int,int> nearest_lex_neighbors(const SuffixArray &sa, const string &pattern) {
    const string &S = sa.str_with_sentinel();
    int n = (int)sa.get_sa().size();
    int L = 0, R = n-1, ansLo = n, ansHi = -1;
    while (L <= R) {
        int mid = (L+R)>>1;
        int pos = sa.get_sa()[mid];
        int cmp = S.compare(pos, pattern.size(), pattern);
        if (cmp < 0) L = mid + 1;
        else { ansLo = mid; R = mid - 1; }
    }
    L = 0; R = n-1;
    while (L <= R) {
        int mid = (L+R)>>1;
        int pos = sa.get_sa()[mid];
        int cmp = S.compare(pos, pattern.size(), pattern);
        if (cmp <= 0) { ansHi = mid; L = mid + 1; }
        else R = mid - 1;
    }
    int prev_pos = (ansLo <= 0) ? -1 : sa.get_sa()[ansLo-1];
    int next_pos = (ansHi+1 >= n) ? -1 : sa.get_sa()[ansHi+1];
    return {prev_pos, next_pos};
}

// 19) Build Suffix Automaton (simple implementation)
// Command: build_sam(s)
// Input: string s
// Output: SAM structure (vector of transitions/states)
// Complexity: O(n * alphabet)
struct SAMState {
    int link = -1;
    int len = 0;
    unordered_map<char,int> next;
};
vector<SAMState> build_sam(const string &s) {
    vector<SAMState> st;
    st.push_back(SAMState()); // root
    int last = 0;
    for (char c : s) {
        int cur = st.size(); st.push_back(SAMState());
        st[cur].len = st[last].len + 1;
        int p = last;
        for (; p != -1 && !st[p].next.count(c); p = st[p].link) st[p].next[c] = cur;
        if (p == -1) st[cur].link = 0;
        else {
            int q = st[p].next[c];
            if (st[p].len + 1 == st[q].len) st[cur].link = q;
            else {
                int clone = st.size(); st.push_back(st[q]);
                st[clone].len = st[p].len + 1;
                for (; p != -1 && st[p].next[c] == q; p = st[p].link) st[p].next[c] = clone;
                st[q].link = st[cur].link = clone;
            }
        }
        last = cur;
    }
    return st;
}

// 20) Flatten grid rows into a single string with separators (helper for 2D string SA)
// Command: concat_rows(rows, sep_char)
// Input: vector<string> rows, separator char
// Output: concatenated string
string concat_rows(const vector<string> &rows, char sep = '\1') {
    string out;
    for (size_t i = 0; i < rows.size(); ++i) {
        out += rows[i];
        if (i + 1 < rows.size()) out.push_back(sep);
    }
    return out;
}

// 21) Find periodic runs using Z-algorithm (simple repeats finder)
// Command: find_runs(s)
// Input: string s
// Output: vector of (start, length, period) for runs found (heuristic)
// Complexity: O(n^2) worst-case (naive check), typically OK for medium n
vector<tuple<int,int,int>> find_runs(const string &s) {
    int n = (int)s.size();
    vector<tuple<int,int,int>> out;
    // naive: for each start and period p, check repeats
    for (int p = 1; p <= n/2; ++p) {
        for (int i = 0; i + p < n; ++i) {
            int len = 0;
            while (i + len + p < n && s[i+len] == s[i+len+p]) ++len;
            if (len >= p) out.emplace_back(i, len + p, p);
        }
    }
    return out;
}

// 22) Circular string matching
// Command: find_in_circular(text, pattern)
// Input: text, pattern
// Output: vector of starting positions in text (0..n-1)
// Complexity: O(n + m) via KMP on text+text
vector<int> find_in_circular(const string &text, const string &pat) {
    int n = (int)text.size(), m = (int)pat.size();
    if (m > n) return {};
    string T = text + text.substr(0, m-1);
    // KMP
    vector<int> pi(m);
    for (int i = 1; i < m; ++i) {
        int j = pi[i-1];
        while (j > 0 && pat[i] != pat[j]) j = pi[j-1];
        if (pat[i] == pat[j]) ++j;
        pi[i] = j;
    }
    vector<int> ans;
    int j = 0;
    for (int i = 0; i < (int)T.size(); ++i) {
        while (j > 0 && (j >= m || T[i] != pat[j])) j = pi[j-1];
        if (T[i] == pat[j]) ++j;
        if (j == m) {
            int st = i - m + 1;
            if (st < n) ans.push_back(st);
            j = pi[j-1];
        }
    }
    sort(ans.begin(), ans.end());
    ans.erase(unique(ans.begin(), ans.end()), ans.end());
    return ans;
}

// 23) Multiple pattern query using SA counts
// Command: sa_multi_count(sa, patterns)
// Input: SA, vector patterns
// Output: vector counts
// Complexity: O(sum |P| * log n)
vector<ll> sa_multi_count(const SuffixArray &sa, const vector<string> &patterns) {
    vector<ll> ans; ans.reserve(patterns.size());
    FMIndex fm(sa);
    for (auto &p : patterns) ans.push_back(fm.count(p));
    return ans;
}

// 24) All borders of a substring [l..r]
// Command: borders_of_substring(s, l, r)
// Input: original string s, inclusive l..r
// Output: vector of border lengths (descending)
// Complexity: O(len)
vector<int> borders_of_substring(const string &s, int l, int r) {
    string sub = s.substr(l, r - l + 1);
    int m = (int)sub.size();
    vector<int> pi(m);
    for (int i = 1; i < m; ++i) {
        int j = pi[i-1];
        while (j > 0 && sub[i] != sub[j]) j = pi[j-1];
        if (sub[i] == sub[j]) ++j;
        pi[i] = j;
    }
    vector<int> res;
    int cur = pi[m-1];
    while (cur > 0) { res.push_back(cur); cur = pi[cur-1]; }
    return res;
}

// 25) Detect if substring S[l..r] is unique in the string
// Command: is_unique_substring(sa, l, r)
// Input: SA, l,r
// Output: bool
// Complexity: O(log n)
bool is_unique_substring(const SuffixArray &sa, int l, int r) {
    const string &S = sa.str_with_sentinel();
    string pat = S.substr(l, r - l + 1);
    FMIndex fm(sa);
    return fm.count(pat) == 1;
}

// 26) Nearest lexicographic matches (already provided above as nearest_lex_neighbors)

// 27) Substring frequency query by indices [l..r]
// Command: substring_freq_query(sa, l, r)
// Input: SA, l,r (0-based original)
// Output: count (ll)
// Complexity: O(|sub| log n)
ll substring_freq_query(const SuffixArray &sa, int l, int r) {
    const string &S = sa.str_with_sentinel();
    string pat = S.substr(l, r - l + 1);
    FMIndex fm(sa);
    return fm.count(pat);
}

// 28) Build Euler-tour + concatenation for tree (helper)
// Command: tree_euler_concat(n, edges, labels, sep)
// Input: n, edges list (0-based), labels per node (string per node), sep char
// Output: concatenated string representing Euler tour with separators
// Complexity: O(n)
string tree_euler_concat(int n, const vector<vector<int>>& adj, const vector<string>& labels, char sep = '\1') {
    string out;
    vector<int> vis(n,0);
    function<void(int)> dfs = [&](int u){
        vis[u]=1;
        out += labels[u];
        out.push_back(sep);
        for (int v: adj[u]) if(!vis[v]) dfs(v);
        out.push_back(sep);
    };
    for (int i = 0; i < n; ++i) if(!vis[i]) dfs(i);
    return out;
}

// 29) DNA indexing helpers: reuse FMIndex and BWT (already implemented)

// 30) LCP stats (max, average, median)
// Command: lcp_stats(sa)
// Input: SA
// Output: tuple(max, average, median)
// Complexity: O(n log n) for median via sort
tuple<int,double,int> lcp_stats(const SuffixArray &sa) {
    vector<int> arr = sa.get_lcp();
    if (arr.size() <= 1) return {0,0.0,0};
    vector<int> v(arr.begin()+1, arr.end());
    int mx = *max_element(v.begin(), v.end());
    double avg = 0;
    for (int x : v) avg += x;
    avg /= v.size();
    sort(v.begin(), v.end());
    int med = v[v.size()/2];
    return {mx, avg, med};
}

// ------------------------ small example usage (demo) ------------------------
int main() {
    string s = "banana";
    SuffixArray sa(s);

    // 1) contains
    cout << "contains 'ana': " << sa_contains(sa, "ana") << "\n";

    // 3) longest repeated
    cout << "LRS: " << sa_longest_repeated(sa) << "\n";

    // 5) longest palindrome
    cout << "Longest palindrome in 'abacdfgdcaba': " << longest_palindrome("abacdfgdcaba") << "\n";

    // 9) kth substring
    cout << "3rd substring: " << sa_kth_substring(sa, 3) << "\n";

    // 14) BWT
    cout << "BWT: " << build_bwt(sa) << "\n";

    // 15) FM-index count
    FMIndex fm(sa);
    cout << "count 'ana' via FM: " << fm.count("ana") << "\n";

    // 16) minimal rotation
    cout << "min rotation of 'bba': " << minimal_rotation("bba") << "\n";

    // 30) lcp stats
    auto [mx, avg, med] = lcp_stats(sa);
    cout << "LCP max=" << mx << " avg=" << avg << " med=" << med << "\n";
    return 0;
}