题目

传送门

给定一个字符串 \(S\)，求 \(S\) 中 \(\forall i\in[0,n)\) 求有多少对后缀满足 \(\text{Len}(lcp)\ge i\)，以及满足条件的两个后缀的权值乘积的最大值.

题解

首先将问题转化为求 \(\text{Len}(lcp)=i\) 的有多少，然后对于第一个询问求后缀和，对于第二个询问求后缀最大.

对于 \(\tt SAM\) 有个性质：对于 \(S\) 中的两个子串，找到它们所属的点 \(u,\;v\)，那么他们的最长公共后缀就是 \(\text{longest}(LCA(u,v))\)，其中 \(LCA(u,v)\) 定义在 \(\text{parent tree}\) 上.

证明略，对于这道题，由于我们要求的是前缀，刚好和性质相反，那么我们考虑把串倒着建 \(\tt SAM\)，对于这个 \(\tt SAM\) 得到的 \(\text{parent tree}\) 的每个点，他们的子树之内所有的点相互匹配，都可以得到刚刚好 \(\text{Len}(lcp)=i\) 的组合，在树上做 \(DP\)（其实不能算 \(DP\)）就可以了.

代码

# include <bits/stdc++.h>
using namespace std;
namespace Elaina{
    # define rep(i,l,r) for(int i=l, i##_end_ = r; i <= i##_end_; ++ i)
    # define fep(i,l,r) for(int i=l, i##_end_ = r; i >= i##_end_; -- i)
    # define fi first
    # define se second
    # define Endl putchar('\n')
    # define writc(x, c) fwrit(x), putchar(c)
    // # define int long long
    typedef long long ll;
    typedef pair<int, int> pii;
    typedef unsigned long long ull;
    typedef unsigned int uint;
    template<class T>inline T Max(const T x, const T y){return x < y ? y : x;}
    template<class T>inline T Min(const T x, const T y){return x < y ? x : y;}
    template<class T>inline T fab(const T x){return x < 0 ? -x : x;}
    template<class T>inline void getMax(T& x, const T y){x = Max(x, y);}
    template<class T>inline void getMin(T& x, const T y){x = Min(x, y);}
    template<class T>T gcd(const T x, const T y){return y ? gcd(y, x % y) : x;}
    template<class T>inline T readin(T x){
        x=0; int f = 0; char c;
        while((c = getchar()) < '0' || '9' < c) if(c == '-') f = 1;
        for(x = (c ^ 48); '0' <= (c = getchar()) && c <= '9'; x = (x << 1) + (x << 3) + (c ^ 48));
        return f ? -x : x;
    }
    template<class T>void fwrit(const T x){
        if(x < 0)return putchar('-'), fwrit(-x);
        if(x > 9)fwrit(x / 10); putchar(x % 10 ^ 48);
    }
}
using namespace Elaina;

const int maxn = 3e5;
const ll inf = (1ll << 60);

int tre[maxn * 2 + 5][26];
int fa[maxn * 2 + 5];
int len[maxn * 2 + 5];
int sz[maxn * 2 + 5];
ll mx[maxn * 2 + 5], mn[maxn * 2 + 5];
int lst = 1, cnt = 1;
inline void add(const int c, const int w){
    int p = lst;
    int u = lst = ++ cnt;
    len[u] = len[p] + 1, sz[u] = 1;
    mx[u] = mn[u] = w;
    for(; p && !tre[p][c]; p = fa[p]) tre[p][c] = u;
    if(!p) fa[u] = 1;
    else{
        int q = tre[p][c];
        if(len[q] == len[p] + 1) fa[u] = q;
        else{
            int nq = ++ cnt;
            mx[nq] = -inf, mn[nq] = inf;
            rep(i, 0, 25) tre[nq][i] = tre[q][i];
            fa[nq] = fa[q], len[nq] = len[p] + 1;
            fa[q] = fa[u] = nq;
            for(; p && tre[p][c] == q; p = fa[p])
                tre[p][c] = nq;
        }
    }
}

struct edge{int to,nxt;
    edge(const int T = 0, const int N = 0) : to(T), nxt(N){}
}e[maxn * 2 + 5];
int tail[maxn * 2 + 5], ecnt;
inline void add_edge(const int u, const int v){
    // printf("u == %d, v == %d\n", u, v);
    e[++ ecnt] = edge(v, tail[u]); tail[u] = ecnt;
}

char s[maxn + 5];
int a[maxn + 5], n;

inline void init(){
    n = readin(1); scanf("%s", s + 1);
    rep(i, 1, n) a[i] = readin(1);
}

// the first query, the count of appearance
ll ans1[maxn + 5];
// the second query, the maximum value to match
ll ans2[maxn + 5];

inline int check(const int u){
    return mx[u] != -inf && mn[u] != inf;
}

void dfs(const int u){
    if(!mx[u]) mx[u] = -inf, mn[u] = inf;
    for(int i = tail[u], v; i; i = e[i].nxt){
        dfs(v = e[i].to);
        ans1[len[u]] += 1ll * sz[u] * sz[v];
        sz[u] += sz[v];
        if(check(u))
            ans2[len[u]] = Max(ans2[len[u]], Max(1ll * mx[u] * mx[v], 1ll * mn[u] * mn[v]));
        mx[u] = Max(mx[u], mx[v]), mn[u] = Min(mn[u], mn[v]);
    }
}

signed main(){
    init();
    fep(i, n, 1) add(s[i] - 'a', a[i]);
    rep(i, 2, cnt) add_edge(fa[i], i);
    rep(i, 0, n + 1) ans2[i] = -inf;
    dfs(1);
    fep(i, n - 1, 0) ans2[i] = Max(ans2[i], ans2[i + 1]), ans1[i] += ans1[i + 1];
    rep(i, 0, n - 1) printf("%lld %lld\n", ans1[i], ans1[i] == 0 ? 0 : ans2[i]);
    return 0;
}

本题关键

\(\tt SAM\) 的性质，对于 \(S\) 中的两个子串，找到它们所属的点 \(u,\;v\)，那么他们的最长公共后缀就是 \(\text{longest}(LCA(u,v))\)，其中 \(LCA(u,v)\) 定义在 \(\text{parent tree}\) 上.