题目详情题解（0）讨论（0）提交记录（0）

AT_abc213_f.[ABC213F] Common Prefixes

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

对于两个字符串 X,YX, Y，它们的相似度 f(X,Y)f(X, Y) 定义为从头开始连续相同的字符数。例如，abc 和 axbc 的相似度为 11，aaa 和 aaaa 的相似度为 33。

给定一个长度为 NN 的字符串 SS。记 SiS_i 表示从第 ii 个字符开始的子串。对于 k=1,…,Nk=1,\ldots,N，请计算 f(Sk,S1)+f(Sk,S2)+…+f(Sk,SN)f(S_k, S_1) + f(S_k, S_2) + \ldots + f(S_k, S_N)。

输入格式

输入通过标准输入给出，格式如下：

NN SS

输出格式

输出 NN 行。

第 ii 行输出 k=ik=i 时问题的答案。

输入输出样例

  • 输入#1

    3
abb

    输出#1

    3
3
2

  • 输入#2

    11
mississippi

    输出#2

    11
16
14
12
13
11
9
7
4
3
4

说明/提示

限制条件

  • 1≤N≤1061 \leq N \leq 10^6
  • SS 是仅由小写英文字母组成的长度为 NN 的字符串

样例解释 1

S1,S2,S3S_1, S_2, S_3 分别为 abb、bb、b。

  • 当 k=1k=1 时，f(S1,S1)+f(S1,S2)+f(S1,S3)=3+0+0=3f(S_1, S_1) + f(S_1, S_2) + f(S_1, S_3) = 3 + 0 + 0 = 3
  • 当 k=2k=2 时，f(S2,S1)+f(S2,S2)+f(S2,S3)=0+2+1=3f(S_2, S_1) + f(S_2, S_2) + f(S_2, S_3) = 0 + 2 + 1 = 3
  • 当 k=3k=3 时，f(S3,S1)+f(S3,S2)+f(S3,S3)=0+1+1=2f(S_3, S_1) + f(S_3, S_2) + f(S_3, S_3) = 0 + 1 + 1 = 2

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页