A5993. LJJ 的字符串
编程题
提高+/省选-
知识点
题目描述
LJJ 拿到了一串来自火星的字符串。
字符串中，每个字符都是一种火星字母，LJJ 将其转换为**小写英文字母 $\texttt{a}\sim \texttt{z}$**，为了便于发现其中的奥秘。
仔细看，这个字符串杂乱中带着有序，有许多重复的片段。于是，LJJ 请来了作为字符串分析专家的你，来帮他分析计算这个字符串的神秘度。
**设 $n$ 是这个字符串的长度。**
**设 $S[i,j]$ 表示字符串 $S$ 中第 $i$ 个位置到第 $j$ 个位置的连续子串（字符串下标从 $1$ 开始）。**
若 $i$ , $j$ , $\text{len}$ 同时满足
* $1\leqslant i<j\leqslant i+\text{len}-1<j+\text{len}-1\leqslant n$
* $S[i,i+\text{len}-1]=S[j,j+\text{len}-1]$
**则这个三元数对 $(i,j,\text{len})$ 对 $S$ 的神秘度的贡献是 $\text{len}$ 。**
输入一个字符串，输出其**所有前缀的神秘度**。**由于这个值过大，所以请对 $10^9+7$ 取模并输出**。
字符串中，每个字符都是一种火星字母，LJJ 将其转换为**小写英文字母 $\texttt{a}\sim \texttt{z}$**，为了便于发现其中的奥秘。
仔细看，这个字符串杂乱中带着有序，有许多重复的片段。于是，LJJ 请来了作为字符串分析专家的你，来帮他分析计算这个字符串的神秘度。
**设 $n$ 是这个字符串的长度。**
**设 $S[i,j]$ 表示字符串 $S$ 中第 $i$ 个位置到第 $j$ 个位置的连续子串（字符串下标从 $1$ 开始）。**
若 $i$ , $j$ , $\text{len}$ 同时满足
* $1\leqslant i<j\leqslant i+\text{len}-1<j+\text{len}-1\leqslant n$
* $S[i,i+\text{len}-1]=S[j,j+\text{len}-1]$
**则这个三元数对 $(i,j,\text{len})$ 对 $S$ 的神秘度的贡献是 $\text{len}$ 。**
输入一个字符串，输出其**所有前缀的神秘度**。**由于这个值过大，所以请对 $10^9+7$ 取模并输出**。
输入格式
输入仅一行：仅由小写字母构成的字符串 $S$。
输出格式
输出共 $n$ 行，第 $i$ 行的整数是前 $i$ 个位置表示的前缀的神秘度。
输入输出样例
输入 #1
aaaaaa
输出 #1
0 0 2 7 19 40
输入 #2
ababab
输出 #2
0 0 0 0 3 10
输入 #3
aabababacbacbac
输出 #3
0 0 0 0 0 3 10 22 22 22 22 22 26 35 50
说明/提示
对于 $20\%$ 的数据，$1\leqslant n\leqslant 1000$；
对于 $40\%$ 的数据，$1\leqslant n\leqslant 5\times 10^5$，且 $S$ 仅由 $\texttt{a}$ 构成；
对于 $60\%$ 的数据，$1\leqslant n\leqslant 10^5$；
对于 $100\%$ 的数据，$1\leqslant n\leqslant 5\times 10^5$。
对于 $40\%$ 的数据，$1\leqslant n\leqslant 5\times 10^5$，且 $S$ 仅由 $\texttt{a}$ 构成；
对于 $60\%$ 的数据，$1\leqslant n\leqslant 10^5$；
对于 $100\%$ 的数据，$1\leqslant n\leqslant 5\times 10^5$。