#PQJ4586x21428. QOJ 4586_21428

    ID: 2973 传统题 3000ms 1024MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:IOI 2027 互测字符串后缀数组二分

QOJ 4586_21428

标题: Far Away Song - Problem - QOJ.ac

#21428. Far Away Song

Statistics

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

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

Far Away Song - anemoi

题目描述

给定一个长度为 n 的字符串 S,下标从 1 开始。记 S(i,j)=SiSi+1⋯Sj,表示 S 从第 i 个字符到第 j 个字符组成的子串。

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

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

  1. 在当前所在的子串中选择一个子串 X。
  2. 选择 X 的一个 Border B,要求 2|B|≥|X|。
  3. 跳到 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 仅包含小写英文字母。