P3426 [POI2005]SZA-Template

    • 148通过
    • 375提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 KMP 树形结构 POI 2005
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB


  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示


    Byteasar wants to put a rather long pattern on his house. In order to do this, he has to prepare an appropriate template with letters cut off first. He is going to put the pattern on the wall by putting the pattern on the wall in the appropriate place and painting over it. This way he can "print" all the letters that are on the template at one time (it is not possible to "print" only some of them). It is, however, possible, to paint some letters on the wall several times, as a result of different applications of the template. The letters on the template are adjacent (there are no spaces on it). Of course, it is possible to prepare a template with the whole pattern on it. But Byteasar would like to minimize the cost, so he wants to make a template as short as possible.

    TaskWrite a programme that:

    reads from the standard input the pattern Byteasar wants to put on his house,determines the minimal length of the template needed to do it,writes the result to the standard output.

    Byteasar 想在墙上涂一段很长的字符,他为了做这件事从字符的前面一段中截取了一段作为模版. 然后将模版重复喷涂到相应的位置后就得到了他想要的字符序列.一个字符可以被喷涂很多次,但是一个位置不能喷涂不同的字符.做一个模版很费工夫,所以他想要模版的长度尽量小,求最小长度是多少.拿样例来说 ababbababbabababbabababbababbaba , 模版为前8个字符ababbaba, 喷涂的过程为: ababbababbabababbabababbababbaba



    In the first and only line of the standard input there is one word. It is the pattern Byteasar wants painted on his house. It consists of no more than $500\ 000$ and no less than $1$ lower-case (non-capital) letters of the English alphabet.


    In the first and only line of the standard output one integer should be written - the minimal number of letters in the template.


    输入样例#1: 复制
    输出样例#1: 复制