#P18754. [2027年国家集训队互测] Far Away Song
[2027年国家集训队互测] Far Away Song
Far Away Song
让我听听你的声音吧,告诉我你旅途中的故事——
无论快乐的事,还是痛苦的事,还有那些铭刻在心的相遇。
Far Away Song - anemoi
题目描述
给定一个长度为 的字符串 ,下标从 开始。记 ,表示 从第 个字符到第 个字符组成的子串。
若非空字符串 同时是字符串 的前缀和后缀,且 ,则称 是 的一个 Border,其中 表示字符串 的长度。
初始时,你位于子串 。每次跳跃按如下方式进行:
-
在当前所在的子串中选择一个子串 。
-
选择 的一个 Border ,要求 。
-
跳到 在 中作为前缀或后缀所对应的子串上,两者任选其一。
例如,当 为 aabaaba,你位于 时,可以选择 abaaba。它的 Border aba 的长度恰好是 的一半,因此你可以跳到 或 。
对于每个 ,请分别求出从 出发、最终到达 时,最多可以进行多少次跳跃。若无法到达,则答案为 。允许不进行任何跳跃。
多组测试数据。
输入格式
第一行包含一个整数 ,表示测试数据组数。
接下来依次输入每组测试数据,对于每组测试数据,输入一行,表示字符串 。
输出格式
对于每组测试数据,输出一行,包含 个整数,第 个整数表示 的答案(若无法到达 ,请输出 -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
解释
第一组数据中, abbababbab,它的长度为 的前缀和后缀均为 abbab。可以进行以下两次跳跃:
-
先跳到 ,再选择 bb,跳到 或 。
-
先跳到 ,再选择 bb,跳到 或 。
只有第一次跳到上述两个 abbab 时,才能继续跳跃,而下一次跳跃只能到达单个字符,因此这四个位置的最大跳跃次数均为 。
其余位置均无法通过跳跃到达,故答案为 。
样例 2
见附件中 wind2.in 和 wind2.ans。此样例满足子任务 3 的约束条件。
样例 3
见附件中 wind3.in 和 wind3.ans。此样例满足子任务 5 的约束条件。
样例 4
见附件中 wind4.in 和 wind4.ans。此样例满足子任务 6 的约束条件。
样例 5
见附件中 wind5.in 和 wind5.ans。此样例满足子任务 8 的约束条件。
数据范围
本题开启合理的子任务依赖。
| 子任务 | 特殊性质 | 分值 | ||
|---|---|---|---|---|
| 无 | ||||
| A | ||||
| B | ||||
| C | ||||
| 无 | ||||
特殊性质 A:存在非空字符串 ,使得 是无限循环串 的前缀,且 。
特殊性质 B: 随机生成,即 的每个字符在大小 的字符集中均匀随机。
特殊性质 C:对于所有 ,均有 。
对于所有数据,保证 ,且单个测试点内所有测试数据的字符串长度之和 。字符串 仅包含小写英文字母。
子任务表:
