#P5268. 加密

    ID: 4306 传统题 1000ms 256MiB 尝试: 12 已通过: 8 难度: 7 上传者: 标签>难度分类提高+/省选-字符串后缀自动机endpos 等价类排序与序列处理计数排序CF2300

加密

加密

题目描述

特工 Star 想用字母加密己方的情报。给定由 NN 个小写字母构成的字符串 SS,下标从 00 开始,按如下方式生成密文:

  1. 光标最初位于下标 00。
  2. 光标位于 ii 时,寻找最长的非空子串 S[j..j+ℓ−1]S[j..j+\ell-1],满足 j<ij<i,且 S[i..i+ℓ−1]=S[j..j+ℓ−1]S[i..i+\ell-1]=S[j..j+\ell-1]。在密文末尾追加两个整数 ℓ,j\ell,j,光标后移 ℓ\ell 位。若最长长度对应多个 jj,选择最小的 jj。
  3. 若不存在这样的非空子串,在密文末尾追加 −1-1 和 S[i]S[i] 的 ASCII 码,光标后移一位。
  4. 光标到达 NN 时,加密结束。

匹配的两个子串可以重叠;只要求前一个子串的起点 j<ij<i,不要求它在 ii 之前结束。

请输出 SS 对应的密文。

输入格式

从标准输入读入一行一个字符串 SS。

输出格式

向标准输出写出一行偶数个用空格隔开的整数,表示密文。

样例

样例输入

tttqqttt

样例输出

-1 116 2 0 -1 113 1 3 3 0

数据范围

数据比例 字符串长度上限
20% N≤300N\le300
40% N≤2000N\le2000
60% N≤5000N\le5000
80% N≤100000N\le100000
100% N≤500000N\le500000