TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2201
  • 题目
  • P2201【KMP或后缀数组】周期
    限制 : 时间限制 : 3000 MS   空间限制 : 65536 KB
    问题描述

    对于字符串S(N个小写字母构成)的每个前缀,我们想知道该前缀是否会周期性的出现(就像循环节)。也就是对于每一个i(2 <= i <= N),我们想知道最大的一个k(k>1,如果存在)使得S的长度为i的前缀可以被写成Ak的形式,也就是连续k个字符串A。

    输入格式

    输入包含若干组测试数据,对于每组测试数据:
    第一行,一个整数N,表示字符串S (2 <= N <= 1 000 000) 的长度
    第二行,一个字符串S
    输入以单独一行,一个数字0作为结束

    输出格式

    对于每组测试数据:
    第一行,输出"Test case #"后面跟测试数据的编号
    接下来若干行,每行对应一个长度为i且满足k>1前缀,输出该前缀的长度和k的值,以空格作为间隔
    结果按前缀长度i升序排列。
    最后输出一个空行作为间隔。

    样例输入

    3
    aaa
    12
    aabaabaabaab
    0

    样例输出

    Test case #1
    2 2
    3 3

    Test case #2
    2 2
    6 2
    9 3
    12 4

    提示

    对于case1:
    长度为2的前缀"aa",可以写成a2,k的值为2
    长度为3的前缀"aaa",可以写成a3, k的值为3

    对于case2:
    长度为2的前缀"aa",可以写成a2,k的值为2
    长度为6的前缀"aabaab",可以写成(aab)2,k的值为2
    长度为9的前缀"aabaabaab",可以写成(aab)3,k的值为3
    长度为12的前缀"aabaabaab",可以写成(aab)4,k的值为4


    来源  KMP求最小循环节