QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB Total points: 100

#8625. dierti

Statistics

杜老师怎么用 txt 写题面,这么敷衍?

dierti.cpp/c/pas dierti.in dierti.out 256MB 1s

两个字符串x,y对S是可区分的当且仅当存在串z,使得xz是S的后缀,yz不是S的后缀,或yz是S的后缀,xz不是S的后缀。

比如"ab"和"b"是对"abbab"是可区分的,取z="ab"即可。

两个后缀x,y不可比较当且仅当对于所有x的非空前缀x1和y的非空前缀y1,x1和y1都是可区分的。比如"ab"和"bab"是不可比较的。

给定一个字符串s,求s的一个尽量大的后缀集合,在集合最大的条件下使集合中串长总和尽量大。

input

多组数据。

每行一个字符串s。

output

每行两个数字,对应s的所求后缀集合的大小和串长总和。

sample in

abbab
aaaaa
abacaba

sample out

2 6
1 5
3 7

hint

分别为(ab,bbab),(aaaaa),(a,ba,caba)。

10%, 每个字符串长度不超过10。
20%, 每个字符串长度不超过20。
另外30%, 所有字符串长度总和不超过5000。
100%, 数据组数不超过1024,读入中s串长总和不超过10^5。