#P18754. [2027年国家集训队互测] Far Away Song

[2027年国家集训队互测] Far Away Song

Far Away Song

让我听听你的声音吧,告诉我你旅途中的故事——

无论快乐的事,还是痛苦的事,还有那些铭刻在心的相遇。

Far Away Song - anemoi

题目描述

给定一个长度为 nn 的字符串 SS,下标从 11 开始。记 S(i,j)=SiSi+1⋯SjS(i, j)=S_iS_{i+1}\cdots S_j,表示 SS 从第 ii 个字符到第 jj 个字符组成的子串。

若非空字符串 BB 同时是字符串 XX 的前缀和后缀,且 ∣B∣<∣X∣|B|<|X|,则称 BB 是 XX 的一个 Border,其中 ∣X∣|X| 表示字符串 XX 的长度。

初始时,你位于子串 S(1,n)S(1, n)。每次跳跃按如下方式进行:

  • 在当前所在的子串中选择一个子串 XX。

  • 选择 XX 的一个 Border BB,要求 2∣B∣≥∣X∣2|B|\ge |X|。

  • 跳到 BB 在 XX 中作为前缀或后缀所对应的子串上,两者任选其一。

例如,当 SS 为 aabaaba,你位于 S(1,7)S(1, 7) 时,可以选择 X=S(2,7)=X=S(2, 7)= abaaba。它的 Border aba 的长度恰好是 ∣X∣|X| 的一半,因此你可以跳到 S(2,4)S(2, 4) 或 S(5,7)S(5, 7)。

对于每个 1≤i≤n1\le i\le n,请分别求出从 S(1,n)S(1, n) 出发、最终到达 S(i,i)S(i, i) 时,最多可以进行多少次跳跃。若无法到达,则答案为 −1-1。允许不进行任何跳跃。

多组测试数据。

输入格式

第一行包含一个整数 TT,表示测试数据组数。

接下来依次输入每组测试数据,对于每组测试数据,输入一行,表示字符串 SS。

输出格式

对于每组测试数据,输出一行,包含 nn 个整数,第 ii 个整数表示 S(i,i)S(i, i) 的答案(若无法到达 S(i,i)S(i, i),请输出 -1)。

样例 1

样例输入

5
abbababbab
bbabbaabbabbaaabab
babbaaaaabaabaaabaaba
baabaabaabaacaabaabaabaacaabaabaabaac
bbaabaaaaabbbbbbbababaabaabaabbabababbbabbabbabbba

样例输出

-1 2 2 -1 -1 -1 2 2 -1 -1
3 3 -1 3 3 2 2 3 3 -1 3 3 2 2 2 -1 -1 -1
-1 -1 1 1 4 4 4 4 4 -1 3 3 -1 3 3 3 -1 3 3 -1 -1
-1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1
1 1 2 2 -1 4 4 4 4 4 6 6 6 6 6 6 6 -1 -1 -1 -1 3 3 -1 3 3 -1 3 3 1 1 -1 -1 -1 -1 -1 2 3 3 -1 3 3 -1 3 3 -1 3 3 2 -1

解释

第一组数据中,S=S= abbababbab,它的长度为 55 的前缀和后缀均为 abbab。可以进行以下两次跳跃:

  • 先跳到 S(1,5)S(1, 5),再选择 S(2,3)=S(2, 3)= bb,跳到 S(2,2)S(2, 2) 或 S(3,3)S(3, 3)。

  • 先跳到 S(6,10)S(6, 10),再选择 S(7,8)=S(7, 8)= bb,跳到 S(7,7)S(7, 7) 或 S(8,8)S(8, 8)。

只有第一次跳到上述两个 abbab 时,才能继续跳跃,而下一次跳跃只能到达单个字符,因此这四个位置的最大跳跃次数均为 22。

其余位置均无法通过跳跃到达,故答案为 −1-1。

样例 2

见附件中 wind2.in 和 wind2.ans。此样例满足子任务 3 的约束条件。

样例 3

见附件中 wind3.in 和 wind3.ans。此样例满足子任务 5 的约束条件。

样例 4

见附件中 wind4.in 和 wind4.ans。此样例满足子任务 6 的约束条件。

样例 5

见附件中 wind5.in 和 wind5.ans。此样例满足子任务 8 的约束条件。

数据范围

本题开启合理的子任务依赖。

子任务 n≤n\le ∑n≤\sum n\le 特殊性质 分值
11 1818 500500 无 55
22 500500 1414
33 5×1035\times 10^3 2121
44 10510^5 1818
55 2×1052\times 10^5 A 1515
66 B 1313
77 C 22
88 无 1212

特殊性质 A:存在非空字符串 PP,使得 SS 是无限循环串 P∞P^{\infty} 的前缀,且 ∣P∣≤10|P|\le 10。

特殊性质 B:SS 随机生成,即 SS 的每个字符在大小 ≥2\ge 2 的字符集中均匀随机。

特殊性质 C:对于所有 1≤i<n1\le i<n,均有 Si≠Si+1S_i\neq S_{i+1}。

对于所有数据,保证 1≤n≤2×1051\le n\le 2\times 10^5,且单个测试点内所有测试数据的字符串长度之和 ∑n≤2×105\sum n\le 2\times 10^5。字符串 SS 仅包含小写英文字母。

子任务表:

子任务表

样例附件 · 全部样例展开