java - 计算字符串中的同构循环移位

Question

我正在尝试解决我有一个 O(n²) 的算法问题时间，O(n)内存解决方案(见下文)而不是 O(n)时间和内存解决方案。

问题是计算给定字符串 s 的同构循环移位数。 循环移位 是初始字符串的转换，例如 if 0 <= k < n (其中 n 是字符串的长度):

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

如果循环移位等于初始字符串，则称其为同构。我有一种感觉，如果一个弦存在于一个模式的重复中，它就可以有这样的循环移位，但我无法证明这一点。如果是这样，那么问题就变成了找到这个模式，然后根据模式的长度和字符串的长度推导出同构循环移位的次数。

我当前的解决方案构建了所有循环移位并将它们与初始字符串进行比较，初始字符串是 O(n)在以 n 为界的循环中操作，导致复杂度为 O(n²) .这是我的 Java 代码供引用:

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、Scala 或伪代码。

Answer 1

我认为你说得对，同构循环移位意味着字符串由重复模式组成。

考虑原始字符串的前 k 个字符，根据循环移位的定义，它们等于原始字符串的后 k 个字符。

现在，考虑原始字符串的后 k 个字符。这些将等于原始字符串的第三个 k 个字符，依此类推，直到您证明该字符串由重复 n/k 次的 k 个字符的模式组成。

现在的问题是在 O(n) 中将字符串识别为重复模式。

一种方法是使用 KMP failure function . failure 函数告诉你在位置 i 匹配的字符串的最长正确前缀。如果您在字符串末尾计算失败函数的值，它会告诉您一个数字 T，它是与字符串后缀匹配的适当前缀的长度。

例如，考虑字符串 ABCABCABC。失败函数将是:

-1 0 0 0 1 2 3 4 5 6

因此字符串末尾的值为 6，这告诉我们重复模式的长度为 p=n-T，在本例中为 9-6=3。

一旦你有了最小重复模式的这个长度，你就可以简单地尝试所有的倍数并检查它们是否除以字符串的长度:

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

总的来说，这是时间和空间上的 O(n)。