TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P2201
  • Problem
  • P2201【KMP】周期
    Limits : Time Limit : 3000 MS   Memory Limit : 65536 KB
    Description

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

    Input Format

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

    Output Format

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

    Sample Input

    3
    aaa
    12
    aabaabaabaab
    0

    Sample Output

    Test case #1
    2 2
    3 3

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

    Hint

    对于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


    Source  KMP求最小循环节