解法二【后缀数组+并查集】见【这里】。
建出后缀树以后，因为任意两个后缀的LCP都是他们的LCA，所以在树上dp，维护大小和最值就可以了。
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
#define LL long long
const int maxn=600010;
const LL oo=5e18;
char s[maxn];
vector<int> son[maxn];
int trans[maxn][27],fa[maxn],val[maxn],a[maxn],
n,tot=1;
LL mn1[maxn],mx1[maxn],mn2[maxn],mx2[maxn],size[maxn],num[maxn],ans[maxn];
void dfs(int u)
{int v;for (vector<int>::iterator it=son[u].begin();it!=son[u].end();++it){v=*it;dfs(v);num[val[u]]+=size[u]*size[v];size[u]+=size[v];if (mn1[v]<=mn1[u]){mn2[u]=mn1[u];mn1[u]=mn1[v];mn2[u]=min(mn2[u],mn2[v]);}else mn2[u]=min(mn2[u],mn1[v]);if (mx1[v]>=mx1[u]){mx2[u]=mx1[u];mx1[u]=mx1[v];mx2[u]=max(mx2[u],mx2[v]);}else mx2[u]=max(mx2[u],mx1[v]);}if (size[u]>=2) ans[val[u]]=max(ans[val[u]],max(mn1[u]*mn2[u],mx1[u]*mx2[u]));
}
int main()
{int last=1,p,np,q,nq,x;scanf("%d",&n);scanf("%s",s+1);for (int i=1;i<=n;i++) scanf("%d",&a[i]);for (int i=1;i<n-i+1;i++) swap(s[i],s[n-i+1]);for (int i=1;i<=n;i++){x=s[i]-'a'+1;val[np=++tot]=val[p=last]+1;last=np;while (p&&!trans[p][x]){trans[p][x]=np;p=fa[p];}if (!p) fa[np]=1;else{q=trans[p][x];if (val[q]==val[p]+1) fa[np]=q;else{val[nq=++tot]=val[p]+1;fa[nq]=fa[q];fa[q]=fa[np]=nq;for (int j=1;j<=26;j++) trans[nq][j]=trans[q][j];while (p&&trans[p][x]==q){trans[p][x]=nq;p=fa[p];}}}}for (int i=1;i<=tot;i++){mn1[i]=mn2[i]=oo;mx1[i]=mx2[i]=-oo;}p=1;for (int i=1;i<=n;i++){p=trans[p][s[i]-'a'+1];mn1[p]=mx1[p]=a[n-i+1];size[p]=1;}for (int i=0;i<n;i++) ans[i]=-oo;for (int i=1;i<=tot;i++) son[fa[i]].push_back(i);dfs(1);for (int i=n-2;i>=0;i--){num[i]+=num[i+1];ans[i]=max(ans[i],ans[i+1]);}for (int i=0;i<n;i++) printf("%lld %lld\n",num[i],ans[i]==-oo?0:ans[i]);
}