CF802I Fake News (hard)
题目描述
现在你已经为 HC $^{2}$ Facebook 页面提出了一条虚假帖子，Heidi 想要在发布之前衡量该帖子的质量。她最近读到一篇（可能是假的）关于分形结构对多媒体消息影响的文章，现在她尝试测量消息的自相似性，自相似性定义如下：
其中，求和针对所有非空字符串 $p$， 表示 $p$ 在 $s$ 中作为子串出现的次数。（注意该求和是无穷的，但实际上只有有限个非零项。）
Heidi 拒绝做任何其他事情，直到她知道如何计算这一自相似性。你能帮她完成吗？（如果你想说服 Heidi，有限字符串不可能是分形 —— 不必尝试，我们已经尝试过了。）
输入格式
输入第一行包含测试用例的数量 $T$（$1 \leq T \leq 10$）。接下来有 $T$ 组测试数据，每组数据包含一行，仅包括小写字母（a-z）组成的字符串 $s$（$1 \leq |s| \leq 100000$）。
输出格式
输出 $T$ 行，每行一个数字，表示相应测试用例的答案。
说明/提示
字符串 $s$ 包含另一个字符串 $p$ 作为子串，意味着 $p$ 是 $s$ 的一个连续子序列。例如，ab 是 cab 的子串，但不是 acb 的子串。
由 ChatGPT 5 翻译