/*
思路:
后缀数组的应用
求r相似的酒的配对方案数和r相似的酒的最大乘积,其实求的是最大公共前缀长度大于等于r的所有后缀的配对方案数以及最大的后缀权值乘积
根据后缀数组的性质, 对于任意i < j, 设lcp(i, j)表示字典序第i和字典序第j的后缀的最长公共前缀的长度,都有如下推论:
lcp(i, j) = min(lcp(i, i+1), lcp(i+1, i+2), ...... , lcp(j-1, j))
所以,对于任意i < j, 如果字典序第i的后缀和字典序第j的后缀满足lcp(i, j) >= r, 那lcp(i, i+1), lcp(i+1, i+2), ...... , lcp(j-1, j)
中每一对都满足大于等于r, 那么整个[i, j]这个区间中任意取两个来配对,都满足r相似,一开始,每一个后缀都看作一个独立的集合,每个集合表示"n相似",
要达到n-1相似,就找height数组中数值是n-1的项,假设height[rk] = n-1, 那排名rk的后缀和排名rk-1的后缀就是n-1相似的,这两个点就可以并成一个
新集合,新集合里面任意取两个数值来配对,都能得到一个n-1相似的合法配对,很显然,新集合里面数值是连续的,下一轮迭代时候,找height中所有数值是
n-2的项,继续合并集合,每一个集合中任选两个数,都是合法的n-2相似的数对,由于原来的集合中数值是连续的,现在新合并集合的时候,只可能将相邻的两个
集合并在一起,所以新集合里面数值还是相邻的,不断迭代下去,就可以用增量的方式求出r相似的集合,r-1相似的集合...... 0相似的集合,只需要维护住
各个集合中数值的最大值,最小值,集合大小,集合中两数乘积的最大值即可,用并查集来维护集合,最大值,最小值,集合大小,集合中两数乘积的最大值这
四个特征值保存到并查集的根节点处即可,这四个特征值在集合合并的时候是可以O(1)复杂度生成新集合的数值的,每一轮迭代都更新全局的答案即可,算法中
涉及到后缀数组的计算,排序,时间复杂度都是O(N*Log(N)), 后续有n轮迭代,均摊到每一轮上,平均每轮只有一次合并集合操作,合并的开销是O(1), 所以迭代
时间复杂度是O(N),整个算法时间复杂度是O(N*Log(N))
*/
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX_STR_LEN = 300005;
char input[MAX_STR_LEN];
int xx[MAX_STR_LEN];
int yy[MAX_STR_LEN];
int c[MAX_STR_LEN];
int sa[MAX_STR_LEN];
int rk[MAX_STR_LEN];
int height[MAX_STR_LEN];
int wei[MAX_STR_LEN]; // 点的权值
long long cnt_ans[MAX_STR_LEN]; // 配对个数答案数组
long long mul_ans[MAX_STR_LEN]; // 最大乘积答案数组
int pp[MAX_STR_LEN]; // 并查集数组
int min_val[MAX_STR_LEN]; // 集合中的最大值
int max_val[MAX_STR_LEN]; // 集合中的最小值
long long mul_val[MAX_STR_LEN]; // 当前集合中的两数乘积的最大值
int set_size[MAX_STR_LEN]; // 集合的大小
const long long MIN_MUL_VAL = -0x7fffffffffffffffLL;
struct Node {
int rank; // 后缀的排名
int prefix_len; // 排名rank和排名rank-1的后缀的最长公共前缀长度
bool operator < (const Node& other) const {
return prefix_len > other.prefix_len;
}
} node_buf[MAX_STR_LEN];
int get_root(int node) {
if (pp[node] == node) {
return node;
}
pp[node] = get_root(pp[node]);
return pp[node];
}
int merge(int node1, int node2) {
int root1 = get_root(node1), root2 = get_root(node2);
if (root1 != root2) {
pp[root1] = root2;
}
return root2;
}
// C(n, 2)组合数
long long get_pair_cnt(int n) {
if (n <= 1) {
return 0LL;
}
return ((long long)n * (long long)(n-1)) >> 1;
}
class SA {
private:
const char* S;
int max_char_val;
bool sa_flag;
bool height_flag;
int str_len;
public:
// 实际计算的时候,为了方便,字符串下标是从1开始的,所以这里S比str错了一位
SA(const char* str, int max_char_val) : S(str-1), max_char_val(max_char_val), sa_flag(false), height_flag(false), str_len(0) { }
int* get_sa() {
int* x = xx;
int* y = yy;
if (sa_flag) {
return sa;
}
int n = strlen(S + 1), m = max_char_val;
str_len = n;
for (int i = 1; i <= n; i ++ )
c[x[i] = S[i]] ++ ;
for (int i = 2; i <= m; i ++ )
c[i] += c[i - 1];
for (int i = n; i; i -- )
sa[c[x[i]] -- ] = i;
for (int k = 1; k <= n; k <<= 1)
{
int num = 0;
for (int i = n - k + 1; i <= n; i ++ )
y[ ++ num] = i;
for (int i = 1; i <= n; i ++ )
if (sa[i] > k)
y[ ++ num] = sa[i] - k;
for (int i = 1; i <= m; i ++ )
c[i] = 0;
for (int i = 1; i <= n; i ++ )
c[x[i]] ++ ;
for (int i = 2; i <= m; i ++ )
c[i] += c[i - 1];
for (int i = n; i; i -- )
sa[c[x[y[i]]] -- ] = y[i], y[i] = 0;
swap(x, y);
x[sa[1]] = 1, num = 1;
for (int i = 2; i <= n; i ++ )
x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++ num;
if (num == n)
break;
m = num;
}
for (int i = 1; i <= n; i ++ )
rk[sa[i]] = i;
sa_flag = true;
return sa;
}
int* get_rk() {
if (!sa_flag) {
get_sa();
}
return rk;
}
int* get_height() {
if (height_flag) {
return height;
}
if (!sa_flag) {
get_sa();
}
int n = str_len;
for (int i = 1, k = 0; i <= n; i ++ )
{
if (rk[i] == 1)
continue;
if (k)
k --;
int j = sa[rk[i] - 1];
while (i + k <= n && j + k <= n && S[i + k] == S[j + k])
k ++ ;
height[rk[i]] = k;
}
height_flag = true;
return height;
}
};
int main() {
//freopen("/Users/grh/Programming/CLionProjects/Algorithm/input.txt", "r", stdin);
int n;
scanf("%d", &n);
scanf("%s", input);
for (int i = 1; i <= n; i++) {
scanf("%d", wei + i);
pp[i] = i;
}
SA algo(input, 150);
int *h_arr = algo.get_height();
int *sa = algo.get_sa();
for (int i = 1; i <= n; i++) {
min_val[i] = max_val[i] = wei[sa[i]];
mul_val[i] = MIN_MUL_VAL;
set_size[i] = 1;
}
for (int i = 0; i < n; i++) {
node_buf[i].rank = i+1;
node_buf[i].prefix_len = h_arr[i+1];
}
sort(node_buf, node_buf + n); // 按照prefix_len降序排列
int pos = 0;
long long cur_cnt = 0;
long long cur_mul = MIN_MUL_VAL;
for (int r = n-1; r >= 0; r--) {
if (pos == n) {
cnt_ans[r] = cur_cnt;
mul_ans[r] = cur_mul;
continue;
}
while (pos < n && node_buf[pos].prefix_len == r) {
int rk = node_buf[pos].rank;
if (rk != 1) {
// 合并两个集合
int root1 = get_root(rk), root2 = get_root(rk-1);
cur_cnt -= get_pair_cnt(set_size[root1]);
cur_cnt -= get_pair_cnt(set_size[root2]);
cur_cnt += get_pair_cnt(set_size[root1] + set_size[root2]);
long long max_mul = MIN_MUL_VAL;
max_mul = max(max_mul, mul_val[root1]);
max_mul = max(max_mul, mul_val[root2]);
max_mul = max(max_mul, (long long)min_val[root1] * (long long)min_val[root2]);
max_mul = max(max_mul, (long long)max_val[root1] * (long long)max_val[root2]);
cur_mul = max(max_mul, cur_mul);
int new_root = merge(root1, root2);
min_val[new_root] = min(min_val[root1], min_val[root2]);
max_val[new_root] = max(max_val[root1], max_val[root2]);
set_size[new_root] = set_size[root1] + set_size[root2];
}
pos++;
}
cnt_ans[r] = cur_cnt;
mul_ans[r] = cur_mul;
}
for (int i = 0; i < n; i++) {
if (mul_ans[i] == MIN_MUL_VAL) {
mul_ans[i] = 0;
}
printf("%lld %lld\n", cnt_ans[i], mul_ans[i]);
}
return 0;
}