QOJ.ac

QOJ

Time Limit: 0.5 s Memory Limit: 256 MB
[+5]

# 464. 前缀函数 / KMP

Statistics

题目描述

给定字符串 S,对每个 i[1,n],定义 πiS[: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