题目描述
给定字符串 S,对每个 i∈[1,n],定义 πi 为 S[:i] 的最长 Border。求数组 π。
输入格式
输入只有一行,包含一个只含有小写字母的字符串 S。
输出格式
输出一行,包含 |S| 个整数,描述 π1,π2,⋯,π|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≤|S|≤105。