vi buildLCP(vi &sa, vi &s, ll &ans, int sz)
{
    int n = s.size();
    vi lcp(n);
    vi pos(n);
    int l = 0;
    for (int i = 0; i < n; ++i)
    {
        pos[sa[i]] = i;
    }
    for (int i = 0; i < n; ++i)
    {
        if (pos[i] == n - 1)
        {
            l = 0;
            continue;
        }
        l = max(l - 1, 0);
        int j = sa[pos[i] + 1];
        while (max(i, j) + l < sz && s[i + l] == s[j + l])
            ++l;
        lcp[pos[i]] = l;
    }
    for (int i = 0; i < sz; ++i)
        ans += lcp[pos[i]];
    return lcp;
}