最新公告
  • 欢迎您光临信息学奥赛网,一个优质的信息学编程题库和信息学编程学习资源专业网站。欢迎加入VIP
  • [POI 2006] Periods of Words

    正文概述 陈老师   2026-01-20 15:14:57  

    题目描述

    一个字符串是由小写英文字母组成的有限序列。特别地,它也可以是空序列(即长度为 00 的序列)。

    如果字符串 AA 是通过字符串 BB 和 CC 按顺序连接(中间没有任何间隔符号)得到的,我们表示为 A=BCA=BC。

    如果存在一个字符串 BB 使得 A=PBA=PB,那么字符串 PP 是字符串 AA 的前缀。此外,如果 P≠AP \neq A 且 PP 不是空字符串,我们称 PP 是 AA 的真前缀。

    如果 QQ 是 AA 的真前缀,并且 AA 是字符串 QQQQ 的前缀(不一定是真前缀),那么字符串 QQ 是 AA 的周期。例如,字符串 abab 和 ababab 都是 abababa 的周期。

    字符串 AA 的最大周期是其最长的周期,如果 AA 没有周期,则为空字符串。例如,ababab 的最大周期是 abab;abc 的最大周期是空字符串。

    编写一个程序,计算该字符串所有前缀的最大周期长度之和。

    输入格式

    第一行包含一个整数 kk,表示字符串的长度。

    接下来的一行包含一个由 kk 个小写英文字母组成的字符串。

    输出格式

    单独一行输出一个整数,表示输入字符串所有前缀的最大周期长度之和。

    8
    babababa
    
    24
    

    数据范围

    对于所有数据,1≤k≤1061\le k\le10^6。

    信息学奥赛网,一个优质的信息学奥赛学习资源平台!
    信息学奥赛网 » [POI 2006] Periods of Words