ACM_Notebook_new

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub ngthanhtrung23/ACM_Notebook_new

:heavy_check_mark: String/tests/lcp.test.cpp

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/number_of_substrings"

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

#include "../SuffixArray.h"

#define REP(i, a) for (int i = 0, _##i = (a); i < _##i; ++i)
#define SZ(x) ((int)(x).size())

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    string s; cin >> s;
    cout << cnt_distinct_substrings(s) << endl;
    return 0;
}
#line 1 "String/tests/lcp.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/number_of_substrings"

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

#line 1 "String/SuffixArray.h"
// Efficient O(N + alphabet_size) time and space suffix array
// For ICPC notebook, it's better to copy a shorter code such as
// https://github.com/kth-competitive-programming/kactl/blob/main/content/strings/SuffixArray.h

// Usage:
// - sa = suffix_array(s, 'a', 'z')
// - lcp = LCP(s, sa)
//   lcp[i] = LCP(sa[i], sa[i+1])
//
// Tested:
// - SA https://judge.yosupo.jp/problem/suffixarray
// - SA https://www.spoj.com/problems/SARRAY/
// - LCP https://judge.yosupo.jp/problem/number_of_substrings
// Suffix Array {{{
// Copied from https://judge.yosupo.jp/submission/52300
// Helper functions {{{
void induced_sort(const std::vector<int>& vec, int val_range,
                  std::vector<int>& SA, const std::vector<bool>& sl,
                  const std::vector<int>& lms_idx) {
    std::vector<int> l(val_range, 0), r(val_range, 0);
    for (int c : vec) {
        if (c + 1 < val_range) ++l[c + 1];
        ++r[c];
    }
    std::partial_sum(l.begin(), l.end(), l.begin());
    std::partial_sum(r.begin(), r.end(), r.begin());
    std::fill(SA.begin(), SA.end(), -1);
    for (int i = (int)lms_idx.size() - 1; i >= 0; --i)
        SA[--r[vec[lms_idx[i]]]] = lms_idx[i];
    for (int i : SA)
        if (i >= 1 && sl[i - 1]) SA[l[vec[i - 1]]++] = i - 1;
    std::fill(r.begin(), r.end(), 0);
    for (int c : vec) ++r[c];
    std::partial_sum(r.begin(), r.end(), r.begin());
    for (int k = (int)SA.size() - 1, i = SA[k]; k >= 1; --k, i = SA[k])
        if (i >= 1 && !sl[i - 1]) {
            SA[--r[vec[i - 1]]] = i - 1;
        }
}

std::vector<int> SA_IS(const std::vector<int>& vec, int val_range) {
    const int n = vec.size();
    std::vector<int> SA(n), lms_idx;
    std::vector<bool> sl(n);
    sl[n - 1] = false;
    for (int i = n - 2; i >= 0; --i) {
        sl[i] = (vec[i] > vec[i + 1] || (vec[i] == vec[i + 1] && sl[i + 1]));
        if (sl[i] && !sl[i + 1]) lms_idx.push_back(i + 1);
    }
    std::reverse(lms_idx.begin(), lms_idx.end());
    induced_sort(vec, val_range, SA, sl, lms_idx);
    std::vector<int> new_lms_idx(lms_idx.size()), lms_vec(lms_idx.size());
    for (int i = 0, k = 0; i < n; ++i)
        if (!sl[SA[i]] && SA[i] >= 1 && sl[SA[i] - 1]) {
            new_lms_idx[k++] = SA[i];
        }
    int cur = 0;
    SA[n - 1] = cur;
    for (size_t k = 1; k < new_lms_idx.size(); ++k) {
        int i = new_lms_idx[k - 1], j = new_lms_idx[k];
        if (vec[i] != vec[j]) {
            SA[j] = ++cur;
            continue;
        }
        bool flag = false;
        for (int a = i + 1, b = j + 1;; ++a, ++b) {
            if (vec[a] != vec[b]) {
                flag = true;
                break;
            }
            if ((!sl[a] && sl[a - 1]) || (!sl[b] && sl[b - 1])) {
                flag = !((!sl[a] && sl[a - 1]) && (!sl[b] && sl[b - 1]));
                break;
            }
        }
        SA[j] = (flag ? ++cur : cur);
    }
    for (size_t i = 0; i < lms_idx.size(); ++i) lms_vec[i] = SA[lms_idx[i]];
    if (cur + 1 < (int)lms_idx.size()) {
        auto lms_SA = SA_IS(lms_vec, cur + 1);
        for (size_t i = 0; i < lms_idx.size(); ++i) {
            new_lms_idx[i] = lms_idx[lms_SA[i]];
        }
    }
    induced_sort(vec, val_range, SA, sl, new_lms_idx);
    return SA;
}
// }}}

template<typename ContainerT = std::string, typename ElemT = unsigned char>
std::vector<int> suffix_array(const ContainerT& s, const ElemT first = 'a',
                         const ElemT last = 'z') {
    std::vector<int> vec(s.size() + 1);
    std::copy(std::begin(s), std::end(s), std::begin(vec));
    for (auto& x : vec) x -= (int)first - 1;
    vec.back() = 0;
    auto ret = SA_IS(vec, (int)last - (int)first + 2);
    ret.erase(ret.begin());
    return ret;
}
// Author: https://codeforces.com/blog/entry/12796?#comment-175287
// Uses kasai's algorithm linear in time and space
std::vector<int> LCP(const std::string& s, const std::vector<int>& sa) {
    int n = s.size(), k = 0;
    std::vector<int> lcp(n), rank(n);
    for (int i = 0; i < n; i++) rank[sa[i]] = i;
    for (int i = 0; i < n; i++, k ? k-- : 0) {
        if (rank[i] == n - 1) {
            k = 0;
            continue;
        }
        int j = sa[rank[i] + 1];
        while (i + k < n && j + k < n && s[i + k] == s[j + k]) k++;
        lcp[rank[i]] = k;
    }
    lcp[n - 1] = 0;
    return lcp;
}
// }}}
// Number of distinct substrings {{{
// Tested:
// - https://judge.yosupo.jp/problem/number_of_substrings
// - https://www.spoj.com/problems/SUBST1/
int64_t cnt_distinct_substrings(const std::string& s) {
    auto lcp = LCP(s, suffix_array(s, 0, 255));
    return s.size() * (int64_t) (s.size() + 1) / 2
        - std::accumulate(lcp.begin(), lcp.end(), 0LL);
}
// }}}
// K-th distinct substring {{{
// Tested:
// - https://cses.fi/problemset/task/2108
// - https://www.spoj.com/problems/SUBLEX/

// Consider all distinct substring of string `s` in lexicographically increasing
// order. Find k-th substring.
//
// Preprocessing: O(N)
// Each query: O(log(N))
//
// Returns {start index, length}. If not found -> {-1, -1}
std::vector<std::pair<int,int>> kth_distinct_substring(
        const std::string& s,
        const std::vector<int64_t>& ks) {
    if (s.empty()) {
        return {};
    }
    auto sa = suffix_array(s, 0, 255);
    auto lcp = LCP(s, sa);
    int n = s.size();
    
    // for each suffix (in increasing order), we count how many new distinct
    // substrings it create
    std::vector<int64_t> n_new_substrs(n);
    for (int i = 0; i < n; ++i) {
        int substr_len = n - sa[i];
        int new_substr_start = (i > 0 ? lcp[i-1] : 0);
        n_new_substrs[i] = substr_len - new_substr_start;
    }
    std::partial_sum(n_new_substrs.begin(), n_new_substrs.end(), n_new_substrs.begin());

    std::vector<std::pair<int,int>> res;
    for (int64_t k : ks) {
        if (k > *n_new_substrs.rbegin()) {
            res.emplace_back(-1, -1);
        } else {
            int i = std::lower_bound(n_new_substrs.begin(), n_new_substrs.end(), k) - n_new_substrs.begin();
            int new_substr_start = (i > 0 ? lcp[i-1] : 0);
            if (i > 0) k -= n_new_substrs[i-1];
            res.emplace_back(sa[i], new_substr_start + k);
        }
    }
    return res;
}
// }}}
// Count substring occurrences {{{
// given string S and Q queries pat_i, for each query, count how many
// times pat_i appears in S
// O(min(|S|, |pat|) * log(|S|)) per query
//
// Tested:
// - (yes / no) https://cses.fi/problemset/task/2102
// - (count) https://cses.fi/problemset/task/2103
// - (position; need RMQ) https://cses.fi/problemset/task/2104
int cnt_occurrences(const string& s, const vector<int>& sa, const string& pat) {
    int n = s.size(), m = pat.size();
    assert(n == (int) sa.size());
    if (n < m) return 0;
 
    auto f = [&] (int start) {  // compare S[start..] and pat[0..]
        for (int i = 0; start + i < n && i < m; ++i) {
            if (s[start + i] < pat[i]) return true;
            if (s[start + i] > pat[i]) return false;
        }
        return n - start < m;
    };
    auto g = [&] (int start) {
        for (int i = 0; start + i < n && i < m; ++i) {
            if (s[start + i] > pat[i]) return false;
        }
        return true;
    };
    auto l = std::partition_point(sa.begin(), sa.end(), f);
    auto r = std::partition_point(l, sa.end(), g);
    // To find first occurrence, return min of sa in range [l, r)
    // See https://cses.fi/problemset/task/2104
    return std::distance(l, r);
}
// }}}
// Count substring occurrences using hash {{{
// If hash array can be pre-computed, can answer each query in
// O(log(|S|) * log(|S| + |pat|)
// Tested
// - https://oj.vnoi.info/problem/icpc22_mt_b
#line 1 "Math/modint.h"
// ModInt {{{
template<int MD> struct ModInt {
    using ll = long long;
    int x;

    constexpr ModInt() : x(0) {}
    constexpr ModInt(ll v) { _set(v % MD + MD); }
    constexpr static int mod() { return MD; }
    constexpr explicit operator bool() const { return x != 0; }

    constexpr ModInt operator + (const ModInt& a) const {
        return ModInt()._set((ll) x + a.x);
    }
    constexpr ModInt operator - (const ModInt& a) const {
        return ModInt()._set((ll) x - a.x + MD);
    }
    constexpr ModInt operator * (const ModInt& a) const {
        return ModInt()._set((ll) x * a.x % MD);
    }
    constexpr ModInt operator / (const ModInt& a) const {
        return ModInt()._set((ll) x * a.inv().x % MD);
    }
    constexpr ModInt operator - () const {
        return ModInt()._set(MD - x);
    }

    constexpr ModInt& operator += (const ModInt& a) { return *this = *this + a; }
    constexpr ModInt& operator -= (const ModInt& a) { return *this = *this - a; }
    constexpr ModInt& operator *= (const ModInt& a) { return *this = *this * a; }
    constexpr ModInt& operator /= (const ModInt& a) { return *this = *this / a; }

    friend constexpr ModInt operator + (ll a, const ModInt& b) {
        return ModInt()._set(a % MD + b.x);
    }
    friend constexpr ModInt operator - (ll a, const ModInt& b) {
        return ModInt()._set(a % MD - b.x + MD);
    }
    friend constexpr ModInt operator * (ll a, const ModInt& b) {
        return ModInt()._set(a % MD * b.x % MD);
    }
    friend constexpr ModInt operator / (ll a, const ModInt& b) {
        return ModInt()._set(a % MD * b.inv().x % MD);
    }

    constexpr bool operator == (const ModInt& a) const { return x == a.x; }
    constexpr bool operator != (const ModInt& a) const { return x != a.x; }

    friend std::istream& operator >> (std::istream& is, ModInt& other) {
        ll val; is >> val;
        other = ModInt(val);
        return is;
    }
    constexpr friend std::ostream& operator << (std::ostream& os, const ModInt& other) {
        return os << other.x;
    }

    constexpr ModInt pow(ll k) const {
        ModInt ans = 1, tmp = x;
        while (k) {
            if (k & 1) ans *= tmp;
            tmp *= tmp;
            k >>= 1;
        }
        return ans;
    }

    constexpr ModInt inv() const {
        if (x < 1000111) {
            _precalc(1000111);
            return invs[x];
        }
        int a = x, b = MD, ax = 1, bx = 0;
        while (b) {
            int q = a/b, t = a%b;
            a = b; b = t;
            t = ax - bx*q;
            ax = bx; bx = t;
        }
        assert(a == 1);
        if (ax < 0) ax += MD;
        return ax;
    }

    static std::vector<ModInt> factorials, inv_factorials, invs;
    constexpr static void _precalc(int n) {
        if (factorials.empty()) {
            factorials = {1};
            inv_factorials = {1};
            invs = {0};
        }
        if (n > MD) n = MD;
        int old_sz = factorials.size();
        if (n <= old_sz) return;

        factorials.resize(n);
        inv_factorials.resize(n);
        invs.resize(n);

        for (int i = old_sz; i < n; ++i) factorials[i] = factorials[i-1] * i;
        inv_factorials[n-1] = factorials.back().pow(MD - 2);
        for (int i = n - 2; i >= old_sz; --i) inv_factorials[i] = inv_factorials[i+1] * (i+1);
        for (int i = n-1; i >= old_sz; --i) invs[i] = inv_factorials[i] * factorials[i-1];
    }

    static int get_primitive_root() {
        static int primitive_root = 0;
        if (!primitive_root) {
            primitive_root = [&]() {
                std::set<int> fac;
                int v = MD - 1;
                for (ll i = 2; i * i <= v; i++)
                    while (v % i == 0) fac.insert(i), v /= i;
                if (v > 1) fac.insert(v);
                for (int g = 1; g < MD; g++) {
                    bool ok = true;
                    for (auto i : fac)
                        if (ModInt(g).pow((MD - 1) / i) == 1) {
                            ok = false;
                            break;
                        }
                    if (ok) return g;
                }
                return -1;
            }();
        }
        return primitive_root;
    }

    static ModInt C(int n, int k) {
        _precalc(n + 1);
        return factorials[n] * inv_factorials[k] * inv_factorials[n-k];
    }
    
private:
    // Internal, DO NOT USE.
    // val must be in [0, 2*MD)
    constexpr inline __attribute__((always_inline)) ModInt& _set(ll v) {
        x = v >= MD ? v - MD : v;
        return *this;
    }
};
template <int MD> std::vector<ModInt<MD>> ModInt<MD>::factorials = {1};
template <int MD> std::vector<ModInt<MD>> ModInt<MD>::inv_factorials = {1};
template <int MD> std::vector<ModInt<MD>> ModInt<MD>::invs = {0};
// }}}
#line 2 "String/hash.h"

// Hash {{{
// Usage:
// HashGenerator g(MAX_LENGTH)
//
// auto h = g.hash(s)
// g.equals(s, h, l1, r1, s, h, l2, r2)
// g.cmp(s, h, l1, r1, s, h, l2, r2)
//
// Tested:
// - https://oj.vnoi.info/problem/substr
// - https://oj.vnoi.info/problem/paliny  - max palin / binary search
// - https://oj.vnoi.info/problem/dtksub  - hash<Hash> for unordered_map
// - https://oj.vnoi.info/problem/vostr   - cmp

const int MOD = 1e9 + 7;
using modular = ModInt<MOD>;

struct Hash {
    long long x;
    modular y;

    Hash operator + (const Hash& a) const { return Hash{x + a.x, y + a.y}; }
    Hash operator - (const Hash& a) const { return Hash{x - a.x, y - a.y}; }
    Hash operator * (const Hash& a) const { return Hash{x * a.x, y * a.y}; }
    Hash operator * (int k) const { return Hash{x*k, y*k}; }

    Hash& operator += (const Hash& a) { return *this = *this + a; }
    Hash& operator -= (const Hash& a) { return *this = *this - a; }
    Hash& operator *= (const Hash& a) { return *this = *this * a; }
};
bool operator == (const Hash& a, const Hash& b) {
    return a.x == b.x && a.y == b.y;
}
bool operator < (const Hash& a, const Hash& b) {
    if (a.x != b.x) return a.x < b.x;
    return a.y.x < b.y.x;
}
std::ostream& operator << (std::ostream& out, const Hash& h) {
    out << '(' << h.x << ", " << h.y << ')';
    return out;
}

// hash function for std::unordered_map
namespace std {
    template<>
    struct hash<Hash> {
        public:
            size_t operator() (const Hash& h) const {
                return h.x * 1000000009 + h.y.x;
            }
    };
}

struct HashGenerator {
    HashGenerator(int maxLen, int base = 311) {
        p.resize(maxLen + 1);
        p[0] = {1, 1};
        for (int i = 1; i <= maxLen; i++) {
            p[i] = p[i-1] * base;
        }
    }

    template<typename Container>
    std::vector<Hash> hash(const Container& s) const {
        std::vector<Hash> res(s.size());
        for (size_t i = 0; i < s.size(); i++) {
            res[i] = p[i] * (int) s[i];
        }
        std::partial_sum(res.begin(), res.end(), res.begin());
        return res;
    }

    Hash getHash(const std::vector<Hash>& h, int l, int r) const {
        return __getHash(h, l, r) * p[p.size() - 1 - l];
    }

    // compare [l1, r1] vs [l2, r2]
    bool equals(
            const std::vector<Hash>& h1, int l1, int r1,
            const std::vector<Hash>& h2, int l2, int r2) const {
        assert(0 <= l1 && l1 <= r1 && r1 < (int) h1.size());
        assert(0 <= l2 && l2 <= r2 && r2 < (int) h2.size());
        if (r1 - l1 != r2 - l2) return false;

        return getHash(h1, l1, r1) == getHash(h2, l2, r2);
    }

    // Returns length of max common prefix of h1[l1, r1] and h2[l2, r2]
    // length = 0 -> first character of 2 substrings are different.
    int maxCommonPrefix(
            const std::vector<Hash>& h1, int l1, int r1,
            const std::vector<Hash>& h2, int l2, int r2) const {
        assert(0 <= l1 && l1 <= r1 && r1 < (int) h1.size());
        assert(0 <= l2 && l2 <= r2 && r2 < (int) h2.size());

        int len1 = r1 - l1 + 1;
        int len2 = r2 - l2 + 1;

        int res = -1, left = 0, right = std::min(len1, len2) - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (equals(h1, l1, l1 + mid, h2, l2, l2 + mid)) {
                res = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return res + 1;
        /* C++20
        auto r = std::views::iota(0, std::min(len1, len2));
        auto res = std::ranges::partition_point(
                r,
                [&] (int mid) {
                    return equals(h1, l1, l1+mid, h2, l2, l2+mid);
                });
        return *res;
         */
    }

    // compare s1[l1, r1] and s2[l2, r2]
    template<typename Container1, typename Container2>
    int cmp(
            const Container1& s1, const std::vector<Hash>& h1, int l1, int r1,
            const Container2& s2, const std::vector<Hash>& h2, int l2, int r2) const {
        assert(0 <= l1 && l1 <= r1 && r1 < (int) h1.size());
        assert(0 <= l2 && l2 <= r2 && r2 < (int) h2.size());

        int commonPrefixLen = maxCommonPrefix(h1, l1, r1, h2, l2, r2);
        char c1 = (l1 + commonPrefixLen <= r1) ? s1[l1 + commonPrefixLen] : 0;
        char c2 = (l2 + commonPrefixLen <= r2) ? s2[l2 + commonPrefixLen] : 0;

        return (c1 == c2) ? 0 : ((c1 < c2) ? -1 : 1);
    }

private:
    std::vector<Hash> p;

    // DO NOT USE, this doesn't divide by p[l]
    Hash __getHash(const std::vector<Hash>& h, int l, int r) const {
        assert(0 <= l && l <= r && r < (int) h.size());
        return h[r] - (l == 0 ? Hash{0, 0} : h[l-1]);
    }
};
// }}}
#line 216 "String/SuffixArray.h"
int cnt_occurrences_hash(
        const vector<int>& sa,        // suffix array
        const HashGenerator& gen,
        const string& s,
        const vector<Hash>& hash_s,   // hash of `s`, generated with `gen`
        const string_view& pat,
        const vector<Hash>& hash_pat  // hash of `pat`, generated with `gen`
        ) {
    int n = s.size(), len = pat.size();
    assert(len == (int) hash_pat.size());
    assert(n == (int) sa.size());
    if (n < len) return 0;

    // f(start) = compare string S[start..] and pat[0..len-1]
    auto f = [&] (int start) {
        return gen.cmp(
                s, hash_s, start, n-1,
                pat, hash_pat, 0, len-1) < 0;
    };
    // g(start) = true if S[start..] == pat[0..]
    auto g = [&] (int start) {
        int max_len = std::min(n - start, len);
        return gen.cmp(
                s, hash_s, start, start + max_len - 1,
                pat, hash_pat, 0, max_len-1) == 0;
    };
    auto l = std::partition_point(sa.begin(), sa.end(), f);
    auto r = std::partition_point(l, sa.end(), g);
    return std::distance(l, r);
}
// }}}
// Returns length of LCS of strings s & t {{{
// O(N)
// Tested:
// - https://www.spoj.com/problems/LCS/
// - https://www.spoj.com/problems/ADAPHOTO/
int longestCommonSubstring(const string& s, const string& t) {
    char c = 127;
    string combined = s + c + t;
    auto sa = suffix_array(combined, 0, 127);
    auto lcp = LCP(combined, sa);
 
    // s -> 0 .. |s|-1
    // 255 -> |s|
    // t -> |s|+1 ..
    int ls = s.size(), lcombined = combined.size();
    auto is_s = [&] (int id) { return sa[id] < ls; };
    auto is_t = [&] (int id) { return sa[id] > ls; };
 
    assert(sa[lcombined - 1] == ls);
 
    int res = 0;
    for (int i = 0; i < lcombined - 2; ++i) {
        if ((is_s(i) && is_t(i+1)) || (is_s(i+1) && is_t(i))) {
            res = max(res, lcp[i]);
        }
    }
    return res;
}
// }}}
// Returns length of LCS of n strings {{{
// Tested:
// - https://www.spoj.com/problems/LCS2/
// - https://www.spoj.com/problems/LONGCS
#line 1 "DataStructure/RMQ.h"
// RMQ {{{
//
// Sparse table
// Usage:
// RMQ<int, _min> st(v);
//
// Note:
// - doesn't work for empty range
//
// Tested:
// - https://judge.yosupo.jp/problem/staticrmq
template<class T, T (*op) (T, T)> struct RMQ {
    RMQ() = default;
    RMQ(const vector<T>& v) : t{v}, n{(int) v.size()} {
        for (int k = 1; (1<<k) <= n; ++k) {
            t.emplace_back(n - (1<<k) + 1);
            for (int i = 0; i + (1<<k) <= n; ++i) {
                t[k][i] = op(t[k-1][i], t[k-1][i + (1<<(k-1))]);
            }
        }
    }

    // get range [l, r-1]
    // doesn't work for empty range
    T get(int l, int r) const {
        assert(0 <= l && l < r && r <= n);
        int k = __lg(r - l);
        return op(t[k][l], t[k][r - (1<<k)]);
    }

private:
    vector<vector<T>> t;
    int n;
};
template<class T> T _min(T a, T b) { return b < a ? b : a; }
template<class T> T _max(T a, T b) { return a < b ? b : a; }
// }}}
#line 281 "String/SuffixArray.h"
int longestCommonSubstring(const std::vector<std::string> strs) {
    char c = 127;
    string combined = "";
    vector<int> ids;
    for (size_t i = 0; i < strs.size(); ++i) {
        const auto& s = strs[i];
        combined += s;
        while (ids.size() < combined.size()) ids.push_back(i);

        combined += c;
        ids.push_back(-1);

        --c;
    }
    auto sa = suffix_array(combined, 0, 127);
    auto lcp = LCP(combined, sa);
    RMQ<int, _min> rmq(lcp);

    // count frequency of i-th string in current window
    std::vector<int> cnt(strs.size(), 0);
    int strs_in_window = 0;
    auto add = [&] (int i) {
        if (i < 0) return;
        ++cnt[i];
        if (cnt[i] == 1) ++strs_in_window;
    };
    auto rem = [&] (int i) {
        if (i < 0) return;
        --cnt[i];
        if (cnt[i] == 0) --strs_in_window;
    };

    int i = 0, j = -1;
    int lcombined = combined.size();
    int n = strs.size();
    int res = 0;
    while (i < lcombined - 1) {
        while (j + 1 < lcombined - 1 && strs_in_window < n) {
            ++j;
            add(ids[sa[j]]);
        }
        if (strs_in_window == n) {
            res = max(res, rmq.get(i, j));
        }

        rem(ids[sa[i]]); ++i;
    }
    return res;
}
// }}}
#line 7 "String/tests/lcp.test.cpp"

#define REP(i, a) for (int i = 0, _##i = (a); i < _##i; ++i)
#define SZ(x) ((int)(x).size())

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    string s; cin >> s;
    cout << cnt_distinct_substrings(s) << endl;
    return 0;
}
Back to top page