我试图解决一个算法问题，我有一个 O（N²）时， O（N）存储解决方案（见下文），而不是一个 O（N）时间和内存解决方案。

I am trying to solve an algorithmic problem for which I have a O(n²) time, O(n) memory solution (see below) instead of a O(n) time and memory solution.

的问题是计算的同构的循环移位的用于给定的字符串的个数。甲的循环移位的是初始串的变换例如如果 0℃= K＆其中; ñ（其中n是字符串的长度）：

The problem is to count the number of isomorphic cyclic shifts for a given string s. A cyclic shift is a transformation of the initial string such as if 0 <= k < n (where n is the length of the string) :

cyclicShift(0) = s
cyclicShift(k) = s[k-1]...s[n-1]s[0]...s[k] if k > 0

一个循环移位所述的同构的，如果它是等于初始字符串。我有一个字符串，可以有这样的循环移位当且仅当它由以图案重复的感觉，但我不能证明这一点。如果是的情况下，这个问题会变得然后找到这个图案，然后推断同构的循环移位的数目，基础上的图案的长度和字符串的长度

A cyclic shift is said isomorphic if it is equal to the initial string. I have the feeling that a string can have such cycling shift iff it consists in the repetition of a pattern, but I cannot prove it. If it was the case, the problem would then become to find this pattern and then deduce the number of isomorphic cyclic shift, basing on the length of the pattern and the length of the string.

我目前的解决方案，构建了所有的循环移位，并比较它们的初始字符串，这是一个 O（N）在用n为界的循环操作，导致 O（N²）的复杂性。这是我的code在Java中，以供参考：

My current solution constructs all the cyclic shifts and compare them to the initial string, which is a O(n) operation in a loop bounded by n, leading to a complexity of O(n²). Here is my code in Java for reference :

public int solution(String S) {
    int count = 1;
    int n     = S.length();

    // We represent the string as a LinkedList to construct the next cyclic shift
    // from a given one with a O(1) time complexity
    List<Character> list = new LinkedList<>();
    for (int i=0 ; i<n ; i++) 
        list.add(S.charAt(i));

    Deque<Character> tmp = new LinkedList<>(list);
    for (int k=1 ; k<n ; k++) {
        tmp.addFirst(tmp.removeLast());
        // this test is O(n) so this solution is O(n^2)
        if (tmp.equals(list))
            count++;
    }

    return count;
}

你有我怎么能解决这个问题，尊重 O（N）要求什么想法？答案可以在Java中，斯卡拉，或伪code。

Do you have any idea of how I could solve this problem respecting the O(n) requirement ? Answers can be in Java, Scala, or pseudo-code.

推荐答案

我觉得你说的很对在同构循环移位意味着字符串包含重复图案的。

I think you are quite right in that an isomorphic cyclic shift means that the string consists of a repeating pattern.

考虑原始字符串的前k个字符，由循环移位它们等于原始字符串的第二ķ字符定义

Consider the first k characters of the original string, by definition of the cyclic shift they are equal to the second k characters of the original string.

现在，考虑原始字符串的第二ķ字符。这些将等于原始字符串的第三个K字符，依此类推，直至已经表明，字符串由k个字符，重复N / K倍的图案。

Now, consider the second k characters of the original string. These will be equal to the third k characters of the original string, and so on until you have shown that the string consists of a pattern of k characters that repeats n/k times.

现在的问题是确定该字符串作为在O（n）的重复图案。

Now the problem is to identify the string as a repeating pattern in O(n).

这样做的一种方式是使用 KMP故障功能。故障功能会告诉你一个相匹配的位置，我该字符串的最长真preFIX。如果您在字符串的结尾计算故障函数的值，它会告诉你一个数T这是一个正确的preFIX该字符串的后缀相匹配的长度。

One way of doing this is to use the KMP failure function. The failure function tells you the longest proper prefix of a string that matches at position i. If you compute the value of the failure function at the end of the string it will tell you a number T which is the length of a proper prefix that matches the suffix of the string.

例如，考虑字符串ABCABCABC。故障功能将是：

For example, consider the string ABCABCABC. The failure function will be:

-1 0 0 0 1 2 3 4 5 6

因此​​，在该字符串的末尾的值是6，这告诉我们，重复图案是长度为p = NT，在这种情况下，9-6 = 3。

So the value at the end of the string is 6, and this tells us that the repeating pattern is of length p=n-T, in this case 9-6=3.

一旦你拥有最小的重复模式这个长度，你可以简单地尝试所有的倍数，并检查它们分割字符串的长度：

Once you have this length of the smallest repeating pattern, you can simply try all multiples and check that they divide the length of the string:

m=p
count=0
while(m<n)
   if n%m==0: count+=1
   m+=p

总的来说，这是O（n）的时间和空间。

Overall this is O(n) in time and space.