【题解】LOJ 2133 「NOI2015」品酒大会

Problem

给定一个字符串 $S$ ,若 $S(l,r)=S(l',r')$ ,则称 $l,l'$ 是 $r-l+1$ 相似的
换句话说,如果两个分别以 $p,q$ 位置为起始位置,长度为 $l$ 的子串完全相同,则称 $p,q$ 为 $l$ 相似的

显然,如果 $p,q$ 为 $l$ 相似的,那么 $p,q$ 也同样为 $[0,l-1]$ 相似的
定义 $a_p*a_q$ 为 $p,q$ 的价值

那么,对于 $r=0,1,2,\cdots,|S|-1$ ,求有多少种方案可选出两组 $r$ 相似的位置,以及其价值最大值

Thought

发现这个东西在 $SAM$ 上敲好求的好伐

将原串反向,那么找相同前缀串变成找相同后缀串,直接搞 $fail$ 树
发现每个节点 $x$ 对于 $(len_{fa[x]},len_x]$ 相似的贡献即 $\frac{siz * (siz+1)}{2}$

至于最大价值,可以保存每个节点的包含的 $endpos$ 集合所对应的最大值,一路合并更新即可

注意到有负值,所以同时把最小值存一下

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 300010;
const int INF = 1000000001;
int read() {
    int ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch -'0'; ch = getchar();}
    return ans * flag;
}
char s[N];
int a[N];
struct SAM {
    long long ans[N], num[N];
    int fa[N << 1], ch[N << 1][26], siz[N << 1], l[N << 1];
    int ma[N << 1] , mi[N << 1];
    int last = 1 , cnt = 1, len;
    int bac[N], ti[N << 1];
    void ins(int c ,int b) {
        int x = last , nx = ++ cnt; last = nx;
        l[nx] = l[x] + 1; siz[nx] = 1; mi[nx] = ma[nx] = b;
        for(; x && !ch[x][c] ; x = fa[x]) ch[x][c] = nx;
        if(!x) fa[nx] = 1;
        else {
            int y = ch[x][c];
            if(l[y] == l[x] + 1) fa[nx] = y;
            else {
                int ny = ++ cnt; l[ny] = l[x] + 1;
                memcpy(ch[ny] , ch[y] , sizeof(ch[y]));
                fa[ny] = fa[y]; fa[y] = fa[nx] = ny;
                for(; ch[x][c] == y ; x = fa[x]) ch[x][c] = ny;
            }
        }
    }
    void insert(char *s) {
        len = strlen(s);
        for(int i = 0 ; i < len ; ++ i) ins(s[i] - 'a' , a[i]);
    }
    void work() {
        memset(ans , 128 , sizeof(ans));
        for(int i = 1 ; i <= cnt ; ++ i) ++ bac[l[i]];
        for(int i = 1 ; i <= len ; ++ i) bac[i] += bac[i - 1];
        for(int i = 1 ; i <= cnt ; ++ i) ti[bac[l[i]] --] = i;
        for(int i = cnt ; i ; -- i) {
            if(!siz[fa[ti[i]]]) {
                ma[fa[ti[i]]] = ma[ti[i]];
                mi[fa[ti[i]]] = mi[ti[i]];
            }
            else {
                ans[l[fa[ti[i]]]] = max(ans[l[fa[ti[i]]]] , 1ll * ma[fa[ti[i]]] * ma[ti[i]]);
                ans[l[fa[ti[i]]]] = max(ans[l[fa[ti[i]]]] , 1ll * mi[fa[ti[i]]] * mi[ti[i]]);
                num[l[fa[ti[i]]]] += 1ll * siz[fa[ti[i]]] * siz[ti[i]];
                ma[fa[ti[i]]] = max(ma[fa[ti[i]]] , ma[ti[i]]);
                mi[fa[ti[i]]] = min(mi[fa[ti[i]]] , mi[ti[i]]);
            }
            siz[fa[ti[i]]] += siz[ti[i]];
        }
        for(int i = len - 1 ; i >= 0 ; -- i) {
            ans[i] = max(ans[i] , ans[i + 1]);
            num[i] += num[i + 1];
        }
        for(int i = 0 ; i < len ; ++ i)
            if(num[i]) printf("%lld %lld\n" , num[i] , ans[i]);
            else puts("0 0");
    }
}sam;
int main() {
    int n = read();
    scanf("%s" , s);
    for(int i = 0 ; i < n ; ++ i) a[i] = read();
    reverse(s , s + n); reverse(a , a + n);
    sam.insert(s);
    sam.work();
    return 0;
}
Comments

添加新评论