相似其实就是两个后缀的公共前缀。
根据题意可以对于两个后缀只算 LCP 的贡献，最后做一下后缀和与后缀最大值。
两个后缀的 LCP 就是后缀树上的 LCA，所以可以对于每个结点统计以它为 LCA 的贡献。
第一问计数比较简单。
第二问最大乘积，由于有负数，所以答案可能是最大值与次大值或最小值与次小值之积。
稍微维护一下即可。
以及注意特判一下大小不到 \(2\) 不可能有贡献的子树。
所以这题用后缀树来做就超水对吧……
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
using namespace std;
const int N = 3e5;
int n,a[N + 5];
char s[N + 5];
int to[(N << 1) + 5],pre[(N << 1) + 5],first[(N << 1) + 5];
inline void add(int u,int v)
{
static int tot = 0;
to[++tot] = v;
pre[tot] = first[u];
first[u] = tot;
}
int sz[(N << 1) + 5],mx[(N << 1) + 5],mx1[(N << 1) + 5],mn[(N << 1) + 5],mn1[(N << 1) + 5];
long long sum[N + 5],ans[N + 5];
struct node
{
int ch[26];
int fa,len;
} sam[(N << 1) + 5];
int whole = 1,tot = 1;
void insert(int x,int w)
{
int cur = whole,p = whole = ++tot;
sam[p].len = sam[cur].len + 1,sz[p] = 1,mx[p] = mn[p] = w;
for(;cur && !sam[cur].ch[x];cur = sam[cur].fa)
sam[cur].ch[x] = p;
if(!cur)
sam[p].fa = 1;
else
{
int q = sam[cur].ch[x];
if(sam[cur].len + 1 == sam[q].len)
sam[p].fa = q;
else
{
int nxt = ++tot;
sam[nxt] = sam[q],sam[nxt].len = sam[cur].len + 1,sam[p].fa = sam[q].fa = nxt;
for(;cur && sam[cur].ch[x] == q;cur = sam[cur].fa)
sam[cur].ch[x] = nxt;
}
}
}
void dfs(int p)
{
int SZ = sz[p];
for(register int i = first[p];i;i = pre[i])
{
dfs(to[i]),SZ += sz[to[i]];
if(mx[p] < mx[to[i]])
mx1[p] = max(mx[p],mx1[to[i]]),mx[p] = mx[to[i]];
else
mx1[p] = max(mx1[p],mx[to[i]]);
if(mn[p] > mn[to[i]])
mn1[p] = min(mn[p],mn1[to[i]]),mn[p] = mn[to[i]];
else
mn1[p] = min(mn1[p],mn[to[i]]);
}
if(SZ < 2)
return ;
ans[sam[p].len] = max(ans[sam[p].len],max((long long)mx[p] * mx1[p],(long long)mn[p] * mn1[p]));
for(register int i = first[p];i;i = pre[i])
sum[sam[p].len] += (long long)sz[p] * sz[to[i]],sz[p] += sz[to[i]];
}
int main()
{
scanf("%d%s",&n,s + 1);
for(register int i = 1;i <= n;++i)
scanf("%d",a + i);
memset(mx,-0x3f,sizeof mx),memset(mx1,-0x3f,sizeof mx1),memset(mn,0x3f,sizeof mn),memset(mn1,0x3f,sizeof mn1),memset(ans,-0x3f,sizeof ans);
for(register int i = n;i;--i)
insert(s[i] - 'a',a[i]);
for(register int i = 1;i <= tot;++i)
add(sam[i].fa,i);
dfs(1);
for(register int i = n - 1;~i;--i)
sum[i] += sum[i + 1],ans[i] = max(ans[i],ans[i + 1]);
for(register int i = 0;i < n;++i)
printf("%lld %lld\n",sum[i],!sum[i] ? 0 : ans[i]);
}