SA

template<typename Str>
struct SuffixArray {
    vector<int> rk,tmp,sa;
    SuffixArray(Str s) {
        int n = s.size();
        sa.resize(n), rk.resize(n), tmp.resize(n);
        iota(all(sa),0);
        for(int i = 0; i < n; i++) rk[i] = s[i];
        for(int L = 1; L < n; L<<=1) {
            auto cmp = [&](int a,int b) {
                if(rk[a] != rk[b]) return rk[a] < rk[b];
                int ra = a+L<n ? rk[a+L] : -1;
                int rb = b+L<n ? rk[b+L] : -1;
                return ra<rb;
            };
            sort(all(sa),cmp);
            tmp[sa[0]] = 0;
            for(int i = 1; i < n; i++) tmp[sa[i]] = tmp[sa[i-1]] + cmp(sa[i-1],sa[i]);
            for(int i = 0; i < n; i++) rk[i] = tmp[i];
        }
    }
};