6

鉴于以下问题：

定义 ：

让 S 是字母 Σ 上的字符串。S'是最小的周期S ifS'是最小的字符串，使得 ：

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

S''的前缀在哪里S。如果没有这样的S'存在，那么S就不是周期性的。

示例：S = abcabcabcabca。Thenabcabc是一个周期 since S = abcabc abcabc a，但最小的周期是abcsince S = abc abc abc abc a。

给出一个算法来找到输入字符串的最小周期S或声明它S不是周期性的。

提示：你可以这样做O(n)...

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

根据问题的定义，S = (S')^k (S'')，那么我认为如果我们创建一个最短周期的自动机，并找到一种方法来找到最短周期，那么我就完成了.

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

任何想法将不胜感激，

问候

4

5 回答 5

1

好的，所以这个问题肯定可以在 O(n) 内解决，我们只需要按照你的建议巧妙地使用 KMP。

解决最长的正确前缀（也是后缀问题）是我们将使用的 KMP 的重要部分。

最长的正确前缀也是一个后缀问题，所以我们暂时称它为前缀后缀问题。

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

“abcabc”的前缀后缀解决方案是“abc”，因为它是最长的字符串，既是正确的前缀又是正确的后缀（正确的前缀和后缀不能是整个字符串）。

“abcabca”的前缀后缀解法是“a”

Hmmmmmmmmm等一下，如果我们只是从“abcabca”的末尾切掉“a”，我们就剩下“abcabc”，如果我们得到这个新字符串的解决方案（“abc”）并再次切掉它，我们就剩下了“abc”嗯嗯嗯嗯嗯。非常有趣。（这几乎是解决方案，但我会谈谈为什么会这样）

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

我将在我的论点中使用一个关键假设：

我们模式的最小周期是我们模式中每个较大周期的有效周期

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

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

模式：“aaaa”

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

模式：“aabbcc”

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

模式：“abcabcabc”

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

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

让l我们的模式的长度，让我们的 lps 数组（ ）k中的最后一个值k=lps[l-1]

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

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

在实践中，您可以使用一个简单的 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 -用于模式搜索的算法/

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;
}

最后但同样重要的是，感谢您发布如此有趣的问题，弄清楚这很有趣！我也是新手，所以如果我的解释的任何部分没有意义，请告诉我。

于 2019-06-29T06:44:14.513 回答
0

我不确定我是否理解您尝试的解决方案。S不过，KMP 是一个有用的子程序——最小的周期是 KMP在完全匹配后移动针线的距离（即）。

于 2013-09-04T21:35:50.707 回答
0

这个问题可以使用 Z 函数来解决，本教程可以帮助你。

于 2015-04-22T17:00:39.120 回答
0

KMP可以轻松解决这个问题

  • 将字符串连接到自身并在其上运行 KMP。
  • 设 n 为原始字符串的长度。
  • 在 KMP 数组中搜索 >= n 的第一个值。该值必须位于 k >= n（从 0 开始）的位置。
  • 那么 k - n + 1 就是字符串中最短周期的长度。

例子：

Original string = abaaba
n = 6
New string = abaabaabaaba
KMP values for this new string: 0 0 1 1 2 3 4 5 6 7 8 9

第一个值 >= n 是 6，位于位置 8。8 - 6 + 1 = 3 是字符串 (aba) 的最短周期的长度。

于 2019-10-19T14:29:21.433 回答
-1

看看这个解决方案是否适用于 O(n)。我使用了字符串的旋转。

public static int stringPeriod(String s){

    String s1= s;
    String s2= s1;

    for (int i=1; i <s1.length();i++){
        s2=rotate(s2);
        if(s1.equals(s2)){
            return i;
        }
    }

    return -1;
}

public static String rotate(String s1){

    String  rotS= s1;

    rotS = s1.substring(1)+s1.substring(0,1);

    return rotS;

}

完整的程序在这个 github 存储库中可用

于 2017-10-07T04:41:18.810 回答