#PQJ4586x21428. QOJ 4586_21428
QOJ 4586_21428
标题: Far Away Song - Problem - QOJ.ac
#21428. Far Away Song
让我听听你的声音吧,告诉我你旅途中的故事——
无论快乐的事,还是痛苦的事,还有那些铭刻在心的相遇。
题目描述
给定一个长度为 n 的字符串 S,下标从 1 开始。记 S(i,j)=SiSi+1⋯Sj,表示 S 从第 i 个字符到第 j 个字符组成的子串。
若非空字符串 B 同时是字符串 X 的前缀和后缀,且 |B|<|X|,则称 B 是 X 的一个 Border,其中 |X| 表示字符串 X 的长度。
初始时,你位于子串 S(1,n)。每次跳跃按如下方式进行:
- 在当前所在的子串中选择一个子串 X。
- 选择 X 的一个 Border B,要求 2|B|≥|X|。
- 跳到 B 在 X 中作为前缀或后缀所对应的子串上,两者任选其一。
例如,当 S 为 aabaaba,你位于 S(1,7) 时,可以选择 X=S(2,7)= abaaba。它的 Border aba 的长度恰好是 |X| 的一半,因此你可以跳到 S(2,4) 或 S(5,7)。
对于每个 1≤i≤n,请分别求出从 S(1,n) 出发、最终到达 S(i,i) 时,最多可以进行多少次跳跃。若无法到达,则答案为 −1。允许不进行任何跳跃。
多组测试数据。
输入格式
第一行包含一个整数 T,表示测试数据组数。
接下来依次输入每组测试数据,对于每组测试数据,输入一行,表示字符串 S。
输出格式
对于每组测试数据,输出一行,包含 n 个整数,第 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= abbababbab,它的长度为 5 的前缀和后缀均为 abbab。可以进行以下两次跳跃:
- 先跳到 S(1,5),再选择 S(2,3)=
bb,跳到 S(2,2) 或 S(3,3)。 - 先跳到 S(6,10),再选择 S(7,8)=
bb,跳到 S(7,7) 或 S(8,8)。
只有第一次跳到上述两个 abbab 时,才能继续跳跃,而下一次跳跃只能到达单个字符,因此这四个位置的最大跳跃次数均为 2。
其余位置均无法通过跳跃到达,故答案为 −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≤ 特殊性质 分值 1 18 500 无 5 2 500 14 3 5×103 5×103 21 4 105 105 18 5 2×105 2×105 A 15 6 B 13 7 C 2 8 无 12
特殊性质 A:存在非空字符串 P,使得 S 是无限循环串 P∞ 的前缀,且 |P|≤10。
特殊性质 B:S 随机生成,即 S 的每个字符在大小 ≥2 的字符集中均匀随机。
特殊性质 C:对于所有 1≤i<n,均有 Si≠Si+1。
对于所有数据,保证 1≤n≤2×105,且单个测试点内所有测试数据的字符串长度之和 ∑n≤2×105。字符串 S 仅包含小写英文字母。