string - 在 O(n) 中找到输入字符串的最小周期？

Question

鉴于以下问题:

Definition :

Let S be a string over alphabet Σ .S' is the smallest period of S if S' is the smallest string such that :

S = (S')^k (S'') ,

where S'' is a prefix of S. If no such S' exists , then S is not periodic .

Example : S = abcabcabcabca. Then abcabc is a period since S =
abcabc abcabc a, but the smallest period is abc since S = abc abc
abc abc a.

Give an algorithm to find the smallest period of input string S or declare that S is not periodic.

Hint : You can do that in O(n) ...

我的解决方案:我们使用 KMP，它在 O(n) 中运行。

根据问题的定义，S = (S')^k (S'') ，那么我认为如果我们创造一个最短周期的自动机，然后想办法找到那个最短周期，然后我就完成了。

问题是自动机的 FAIL 箭头放在哪里……

任何想法将不胜感激，

问候

Answer 1

好吧，这个问题绝对可以在 O(n) 中解决，我们只需要按照您的建议巧妙地使用 KMP。

解决最长的正确前缀这也是一个后缀问题是我们将使用的 KMP 的重要组成部分。

longest proper prefix which is also a suffix problem 太啰嗦了，所以我们暂时称它为前缀后缀问题。

前缀后缀问题可能很难理解，所以我将包含一些示例。

The prefix suffix solution for "abcabc" is"abc" since that is the longest string which is both a proper prefixand a proper suffix (proper prefixes and suffixes cannot be the entirestring).

The prefix suffix solution for "abcabca" is "a"

Hmmmmmmmmmm 等一下，如果我们只是从“abcabca”的末尾砍掉“a”，我们就剩下“abcabc”，如果我们得到这个新的解决方案(“abc”)字符串并再次将其切掉，我们剩下“abc”Hmmmmmmmmm。非常有趣。(这几乎是解决方案，但我将讨论为什么它有效)

好吧，让我们尝试将这种直觉形式化一点，看看我们是否能找到解决方案。

我将在我的论证中使用一个关键假设:

The smallest period of our pattern is a valid period of every larger period in our pattern

让我们将模式的前 i 个字符的前缀后缀解决方案存储在 lps[i] 中。这个 lps 数组可以在 O(n) 中计算，并用在 KMP 算法中，您可以阅读更多关于如何在 O(n) 中计算它的信息) 这里:https://www.geeksforgeeks.org/kmp-algorithm-for-pattern-searching/

为了清楚起见，我将列出一些lps 数组的示例

Pattern:"aaaaa"

lps: [0, 1, 2, 3, 4]

Pattern:"aabbcc"

lps: [0, 1, 0, 0, 0, 0]

Pattern:"abcabcabc"

lps: [0, 0, 0, 1, 2, 3, 4, 5, 6]

好吧，现在让我们定义一些变量，以帮助我们找出为什么这个 lps 数组有用。

Let l be the length of our pattern, and let k be the last value in our lps array(k=lps[l-1])

值 k 告诉我们字符串的前 k 个字符与字符串的最后 k 个字符相同。我们可以使用这个事实来找到一个时期!

使用此信息，我们现在可以证明由字符串的前 l-k 个字符组成的前缀构成了一个有效句点。这很清楚，因为不在我们前缀中的下一个 k 字符必须匹配我们前缀的前 k 个字符，因为我们如何定义我们的 lps数组。我们前缀中的前 k 个字符必须与构成我们后缀的最后 k 个字符相同。

在实践中，您可以使用一个简单的 while 循环来实现这一点，如下所示，其中 index 标记您当前认为是最小句点的后缀的结尾。

public static void main(String[] args){
    String pattern="abcabcabcabca";
    int[] lps= calculateLPS(pattern);
    //start at the end of the string
    int index=lps.length-1;
    while(lps[index]!=0){
        //shift back
        index-=lps[index];
    }
    System.out.println(pattern.substring(0,index+1));
}

并且由于计算 lps 发生在 O(n) 中，并且您总是在 while 循环中至少向后移动 1 步，因此整个过程的时间复杂度为简单的 O(n)

如果您想在下面查看我的确切代码，我在我的 calculateLPS() 方法中大量借鉴了 KMP 的 geeksForGeeks 实现，但我建议您也看看他们的解释:https://www.geeksforgeeks.org/kmp-algorithm-for-pattern-searching/

static int[] calculateLPS(String pat) {
    int[] lps = new int[pat.length()];
    int len = 0;
    int i = 1;
    lps[0] = 0;

    while (i < pat.length()) {
        if (pat.charAt(i) == pat.charAt(len)) {
            len++;
            lps[i] = len;
            i++;
        }
        else {
            if (len != 0) {
                len = lps[len - 1];
            }
            else {
                lps[i] = len;
                i++;
            }
        }
    }
    System.out.println(Arrays.toString(lps));
    return lps;
}

最后但同样重要的是，感谢您发布如此有趣的问题，解决这个问题非常有趣!另外，我对此并不陌生，所以如果我的解释有任何不合理之处，请告诉我。