#P6794. [2019福建夏令营]串

    ID: 6616 传统题 1500ms 128MiB 尝试: 2 已通过: 1 难度: 8 上传者: 标签>难度分类提高+/省选-字符串回文树后缀数组Kasai 算法LCP+RMQ数据结构ST 表有序集合排序与序列处理自定义排序规则模拟与实现技巧增量维护CF2500

[2019福建夏令营]串

串(string)

题目描述

给定一个长度为 nn 的字符串 SS。

如果非空字符串 TT 是 SS 中某个回文子串的前缀,则称 TT 为 SS 的一个好子串。定义 F(S)F(S) 为本质不同的好子串个数,其中本质不同指字符串内容不同。

记 SiS_i 为 SS 的前 ii 个字符组成的前缀。对每个 i=1,2,…,ni=1,2,\ldots,n,求 F(Si)F(S_i)。

这里的回文子串可以位于 SiS_i 的任意位置;不同位置产生的相同好子串只计一次。

输入格式

第一行一个正整数 nn。

第二行一个长度为 nn、由小写英文字母组成的字符串 SS。

输出格式

输出 nn 行,第 ii 行一个整数,表示 F(Si)F(S_i)。答案不取模。

样例输入

8
bccbbbbc

样例输出

1
2
3
6
7
8
9
14

数据范围

  • 对于 10%10\% 的数据,n≤100n\le100。
  • 对于 20%20\% 的数据,n≤1000n\le1000。
  • 对于 30%30\% 的数据,n≤10000n\le10000。
  • 对于 40%40\% 的数据,n≤50000n\le50000。
  • 对于 70%70\% 的数据,n≤105n\le10^5。
  • 对于所有数据,n≤3×105n\le3\times10^5。