/ Vijos / 题库 /

陶陶的名字

陶陶的名字

背景

陶陶是一个智能机器人,他能像人一样思考问题,不过由于IQ问题,他给自己取了一个很长很长的名字。

描述

某一天,陶陶想把自己的名字涂在墙上。由于他的名字太长,为了省事,他从自己名字的开头截取了一段作为模板。我们不妨设这个模板的长度为l,陶陶的名字的长度为L,那么有1≤l≤L。然后陶陶会用这个模板进行若干次喷涂,喷出自己的名字(后一次喷涂会覆盖前一次喷涂的结果,例如当前墙上已经有abc三个字符,那么如果在c处进行喷涂,就会得到ababc)。陶陶喷涂名字总是从前向后喷的,假设陶陶喷涂了k次,这k次喷涂按时间顺序第i次喷涂的位置是s[i],那么s[i]<s[i+1]。

格式

输入格式

输入文件的仅包含一行,为陶陶的名字。

输出格式

输出文件仅包含一行,ans,表示最短的模版长度。

样例1

样例输入1

abcabababc

样例输出1

3

限制

1秒

提示

【样例解释】
陶陶的名字是abcabababc,最短的模版是abc。按如下方式喷涂出陶陶的名字:

图片

注意,印刷只能从前向后印,不能这样印:

图片

【约定】
对于10%的数据, n≤200
对于30%的数据, n≤1000
对于100%的数据,n≤1000000

来源

原创题。

信息

ID
1677
难度
8
分类
字符串 | KMP 点击显示
标签
递交数
2259
已通过
198
通过率
9%
上传者

相关

在下列比赛中:

第一届Curimit模拟赛