CF204E Little Elephant and Strings 题解

· · 个人记录

对于一个串 a_i，从左到右枚举 l，则满足条件的最远 r 单调后移，

于是可以双指针统计，只需要统计当前两个指针之间的子串被多少个串包含。

建广义 SAM，维护 c_i 表示 i 节点被多少个串包含。

对一个串 a_i，它会使它所有前缀对应的节点的 fail 树根链覆盖到的所有节点 c 值加一。

也就是说，我们需要对根链并加一。

把这些根链按端点 DFS 序排序，每次把一条根链的端点到它与上一条根链的端点的 LCA 这条树链加一即可。

#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
struct E
{
    int v, t;
} e[200050];
int T, k, n, o, z, _, __, b[200050], V[200050], l[200050], d[200050], g[200050], h[200050], f[200050][25], c[200050][26];
string u[200050];
void A(int u, int v) { e[++__] = {v, h[u]}, h[u] = __; }
void I(int x)
{
    int u = ++o, p = z;
    l[u] = l[z] + 1;
    while (p != -1 && !c[p][x])
        c[p][x] = u, p = f[p][0];
    if (p == -1)
        f[u][0] = 0;
    else
    {
        int q = c[p][x];
        if (l[p] + 1 == l[q])
            f[u][0] = q;
        else
        {
            int w = ++o;
            l[w] = l[p] + 1;
            f[w][0] = f[q][0];
            for (int i = 0; i < 26; ++i)
                c[w][i] = c[q][i];
            while (p != -1 && c[p][x] == q)
                c[p][x] = w, p = f[p][0];
            f[q][0] = f[u][0] = w;
        }
    }
    z = u;
}
void D(int u)
{
    b[u] = ++_;
    for (int i = h[u], v; i; i = e[i].t)
    {
        d[v = e[i].v] = d[u] + 1;
        for (int j = 1; f[v][j - 1]; ++j)
            f[v][j] = f[f[v][j - 1]][j - 1];
        D(v);
    }
}
int L(int x, int y)
{
    if (d[x] < d[y])
        swap(x, y);
    while (d[x] > d[y])
        x = f[x][__lg(d[x] - d[y])];
    if (x == y)
        return x;
    for (int k = __lg(d[x]); k >= 0; --k)
        if (f[x][k] != f[y][k])
            x = f[x][k], y = f[y][k];
    return f[x][0];
}
void S(int u, int k)
{
    for (int i = h[u], v; i; i = e[i].t)
        if ((v = e[i].v) != k)
            S(v, u), V[u] += V[v];
}
bool C(int x, int y) { return b[x] < b[y]; }
int main()
{
    f[0][0] = -1;
    scanf("%d%d", &T, &k);
    for (int i = 1; i <= T; ++i)
    {
        cin >> u[i];
        z = 0;
        for (auto j : u[i])
            I(j - 'a');
    }
    for (int i = 1; i <= o; ++i)
        A(f[i][0], i);
    d[0] = 1;
    D(0);
    for (int i = 1; i <= T; ++i)
    {
        for (int j = 0, p = 0; j < u[i].length(); ++j)
            p = c[p][u[i][j] - 'a'], g[j] = p;
        sort(g, g + u[i].length(), C);
        for (int j = 0; j < u[i].length(); ++j)
        {
            ++V[g[j]];
            if (j)
                --V[L(g[j], g[j - 1])];
        }
    }
    S(0, -1);
    for (int i = 1; i <= T; ++i)
    {
        long long q = 0;
        for (int l = 1, r = 0, p = 0; l <= u[i].length(); ++l)
        {
            if (r < l - 1)
                r = l - 1, p = 0;
            while (r < u[i].length() && V[c[p][u[i][r] - 'a']] >= k)
                p = c[p][u[i][r++] - 'a'];
            q += r - l + 1;
            if (l <= r && r - l + 1 == ::l[f[p][0]] + 1)
                p = f[p][0];
        }
        printf("%lld ", q);
    }
    return 0;
}