#P9721. string

    ID: 6347 传统题 2000ms 512MiB 尝试: 3 已通过: 1 难度: 7 上传者: 标签>CF2300提高+/省选-后缀自动机endpos 等价类计数排序滑动窗口

string

题目描述

给定一个由 0 和 1 组成的字符串 SS,下标从 00 开始。对于每个下标 ii,求以 ii 为右端点的最长子串长度 LL,使这个子串还在它的左侧完整出现过。两个出现位置不能重叠。若没有这样的非空子串,答案为 00。

具体地说,求最大的整数 L≥1L\ge1,使得存在 kk 满足 0≤k0\le k、k+L≤i−L+1k+L\le i-L+1,并且 S[k…k+L−1]=S[i−L+1…i]S[k\ldots k+L-1]=S[i-L+1\ldots i]。

原 PDF 题面

输入格式

一行一个非空二进制字符串 SS。

输出格式

输出 ∣S∣|S| 行,第 i+1i+1 行为下标 ii 的答案。

样例

100101010111001
0
0
1
1
2
2
2
2
3
4
1
1
2
3
4
0000001111111010101010101
0
1
1
2
2
3
0
1
1
2
2
3
3
1
2
2
2
2
3
4
4
4
5
6
6

数据范围

| 测试点 | ∣S∣|S| 上限 | | --- | ---: | | 1–2 | 600 | | 3–5 | 3,000 | | 6–11 | 10510^5 | | 12–14 | 4×1054\times10^5 | | 15–17 | 7×1057\times10^5 | | 18–25 | 10610^6 |

原 PDF 的公式使用长度减一作为下标参数。本站按原样例与评测数据输出实际长度 LL。