QOJ.ac

QOJ

Time Limit: 0.5 s Memory Limit: 256 MB
Statistics

题目描述

给定字符串 $S$,对每个 $i \in [1, n]$,定义 $\pi_i$ 为 $S[:i]$ 的最长 Border。求数组 $\pi$。

输入格式

输入只有一行,包含一个只含有小写字母的字符串 $S$。

输出格式

输出一行,包含 $|S|$ 个整数,描述 $\pi_1, \pi_2, \cdots, \pi_{|S|}$。

样例数据

样例 1 输入

abcababcababcbacbabc

样例 1 输出

0 0 0 1 2 1 2 3 4 5 6 7 8 0 1 0 0 1 2 3

样例 2

见下发文件

样例 3

见下发文件

子任务

对于所有数据,$1 \leq |S| \leq 10^5$。