题目 30003

Z 算法

查看题解 ↗GitHub ↗如何评测
题号
30003
时间限制
10000 ms
内存限制
1024 MB
标签
字符串
来源
Library Checker (yosupo06) - zalgorithm

【题目描述】

给定一个长度为 NN 的字符串 SS。按如下方式计算数组 a0,a1,...,aN−1a_0, a_1, ..., a_{N - 1}:

  • aia_i 是 SS 与 S.substr(i)S.substr(i) 的最长公共前缀(LCP)。

【输入】

文本
$S$

【输出】

文本
$a_0$ $a_1$ $a_2$ ... $a_{N-1}$

【输入样例】

文本
abcbcba

【输出样例】

文本
7 0 0 0 0 0 1

【输入样例2】

文本
mississippi

【输出样例2】

文本
11 0 0 0 0 0 0 0 0 0 0

【输入样例3】

文本
ababacaca

【输出样例3】

文本
9 0 3 0 1 0 1 0 1

【输入样例4】

文本
aaaaa

【输出样例4】

文本
5 4 3 2 1

【数据范围】

  • 1≤N≤5000001 \leq N \leq 500000
  • SS 的每个字符均为小写英文字母。

【来源】

Library Checker(yosupo06) zalgorithm

数据下载

题目 30003 的公开数据

正在读取文件列表…

常用命令

题目 30003 的 ROJ 命令

以下命令默认使用全局安装的 ROJ Skill,请在终端中直接执行;如果修改过 AGENT_HOME,请将命令中的 ~/.agents 替换为对应目录。