题目描述

一个字符串的前缀是从第一个字符开始的连续若干个字符，例如 abaab 共有 5 个前缀，分别是 a，ab，aba，abaa，abaab。

我们希望知道一个 N 位字符串 S 的前缀是否具有循环节。

换言之，对于每一个从头开始的长度为 i（i>1）的前缀，是否由重复出现的子串 A 组成，即 AAA…A （A 重复出现 K 次,K>1）。

如果存在，请找出最短的循环节对应的 K 值（也就是这个前缀串的所有可能重复节中，最大的 K 值）。

输入格式
输入包括多组测试数据，每组测试数据包括两行。

第一行输入字符串 S 的长度 N。

第二行输入字符串 S。

输入数据以只包括一个 0 的行作为结尾。

输出格式
对于每组测试数据，第一行输出 Test case # 和测试数据的编号。

接下来的每一行，输出具有循环节的前缀的长度 i 和其对应 K，中间用一个空格隔开。

前缀长度需要升序排列。

在每组测试数据的最后输出一个空行。

数据范围
2≤N≤1000000

样例

输入样例：
3
aaa
4
abcd
12
aabaabaabaab
0
输出样例：
Test case #1
2 2
3 3

Test case #2

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

算法1

(暴力枚举)

时间复杂度

参考文献

JAVA 代码

//万能开头：
import java.util.Scanner;
import java.lang.Math;
import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;
import java.lang.Comparable;
import java.util.Comparator;
import java.util.Collections;
import java.util.Arrays;
import java.util.Map;
import java.util.HashMap;
import java.util.NavigableMap;
import java.util.TreeMap;
import java.util.PriorityQueue;
import java.util.Queue;
class Main{
    static class KmpTemplate {
        final String source;
        final String pattern;

        public KmpTemplate(String source, String pattern) {
            this.source = source;
            this.pattern = pattern;
            onConstructor();
        }

        void onConstructor() {
            if (pattern == null) {
                throw new IllegalStateException("pattern npe");
            }
            if (source == null || source.isEmpty()) {
                throw new IllegalStateException("source npe");
            }

        }

        public int[] getNextArr() {
            int[] next = new int[pattern.length()];
            for (int i = 1, j = 0; i < pattern.length(); i++) {
                while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) j = next[j - 1];
                if (pattern.charAt(i) == pattern.charAt(j)) j++;
                next[i] = j;
            }
            return next;
        }

        public int[] getNextArr2() {
            int n =pattern.length();
            int[] next = new int[n+1];
            for (int i = 2, j = 0; i <= n; i++) {
                while (j > 0 && pattern.charAt(i) != pattern.charAt(j+1)) j = next[j];
                if (pattern.charAt(i) == pattern.charAt(j+1)) j++;
                next[i] = j;
            }
            return next;
        }

        /**
         * @return -1 没有找到
         */
        public int indexOf() {
            if (pattern.isEmpty()) return 0;
            int[] next = getNextArr();
            for (int i = 0, j = 0; i < source.length(); i++) {
                while (j > 0 && source.charAt(i) != pattern.charAt(j)) j = next[j - 1];
                if (source.charAt(i) == pattern.charAt(j)) j++;
                if (j == pattern.length()) {
                    return i - pattern.length() + 1;
                }
            }
            return -1;
        }

        public static int[] getNextArr(String pattern) {
            return new KmpTemplate("test", pattern).getNextArr();
        }

        public static int indexOf(final String source, final String target) {
            return new KmpTemplate(source, target).indexOf();
        }

        public static boolean contains(final String source, final String target) {
            return indexOf(source, target) > -1;
        }
    }

    static Scanner sc = new Scanner(System.in);
    public static void main(String[] args) {
        int cnt = 1;
        int T=0;
        while((T=sc.nextInt()) > 0){
            int[] next = KmpTemplate.getNextArr(sc.next());
            System.out.println("Test case #"+cnt++);
            for(int i=1;i<next.length;i++){
                int t = i - next[i];
                if(t != i && (i+1) % (t+1) == 0)System.out.println((i+1)+" "+((i+1) / (t+1)));
            }
            System.out.println();
        }
    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla