在单词中寻找最短的重复周期？

Question

我将要编写一个函数，它将返回一个最短周期的字母组合，这个组合最终可以创建给定的单词。

例如，单词abkebabkebabkeb是由重复的abkeb单词创建的。我想知道如何高效地分析输入的单词，以获取创建输入单词的最短字符周期。

- jack44

---

@Tony The Tiger，结果（最短时间）不必是一个真实的单词。 - jack44

Answer 1

这里是一个正确的O(n)算法。第一个for循环是KMP算法中构建表的部分。有多种证明表明它总是在线性时间内运行。

由于这个问题已经有了4个之前的答案，其中没有一个是O(n)和正确的，我对这个解决方案进行了严格的测试，以确保其正确性和运行时间。

def pattern(inputv):
    if not inputv:
        return inputv

    nxt = [0]*len(inputv)
    for i in range(1, len(nxt)):
        k = nxt[i - 1]
        while True:
            if inputv[i] == inputv[k]:
                nxt[i] = k + 1
                break
            elif k == 0:
                nxt[i] = 0
                break
            else:
                k = nxt[k - 1]

    smallPieceLen = len(inputv) - nxt[-1]
    if len(inputv) % smallPieceLen != 0:
        return inputv

    return inputv[0:smallPieceLen]

- Buge

---

这是你自己想出来的解决方案还是已知算法？ - davidbuttar

KMP是一个已知的算法。这个问题与我曾经作业中遇到的问题非常相似，下面是我给出的答案。虽然我的讲师用了稍微不同的方法，但也使用了KMP算法。 - Buge

@LinMa:（Buge最近不活跃了）nxt[-1]的意思是如果整个字符串不匹配，我们将使用什么索引来进行下一次比较。这是在所有模式都匹配并且您想在更长的文本中找到其下一个出现时要比较的索引。nxt[i]=p表示pattern[i+1-p:i+1]等于pattern[0:p]（对于p+1而言则不相等）。如果“第一个”不匹配是“在len+1”的位置，则nxt[-1]是下一个要比较的索引。（在许多KMP的演示/实现中，索引0处有一个特殊值-1，n值如上所述“向右移动一个索引”。） - greybeard

@LinMa：（无论如何）让我把 len(inputv) 称为 _len_，nxt[-1] 称为 _matchLen_。如果 matchLen < _smallPieceLen_，那么 smallPieceLen 能够整除 len 的唯一机会就是等于它本身。如果 smallPieceLen ≤ _matchLen_，则 inputv[0:smallPieceLen] 等于 inputv[smallPieceLen:2*smallPieceLen]，并且 k 没有被重置（再次）：inputv 由 inputv[0:smallPieceLen] 的重复组成 - 可被整除性检查只是确保它以完整的重复结束。 - greybeard

@Boris 我认为[1, 2]是错误的。问题说：“例如，单词abkebabkebabkeb是由重复的abkeb单词创建的。”但是不可能通过重复[1, 2]来创建[1, 2, 1]。你需要重复它，然后截掉末尾才能得到[1, 2, 1]。但是，是的，这个问题在关于[1, 2, 1]的正确答案方面有些模糊。 - Buge

Answer 2

这是一个关于PHP的例子：

<?php
function getrepeatedstring($string) {
    if (strlen($string)<2) return $string;
    for($i = 1; $i<strlen($string); $i++) {
        if (substr(str_repeat(substr($string, 0, $i),strlen($string)/$i+1), 0, strlen($string))==$string)
            return substr($string, 0, $i);
    }
    return $string;
}
?>

- AndersTornkvist

---

这将返回“abkeb”，这应该是正确的，但我不确定OP是以何种方式要求“kebab”而不是“abkeb”。 - pimvdb

这正是我要找的。但它的时间复杂度为O(n)。有什么想法可以加速吗？ - jack44

@jack44：除非你检查了整个字符串，否则你无法知道是否有最短的循环。除非你拥有其他知识，比如可能的最大循环是什么。也许字符串中的最后一个字符会打乱整个循环，你不知道。 - mellamokb

我不懂PHP，但是这看起来像是O(n^2)的时间复杂度。 - dfb

@jack44 速度可以提高。一种解决方案是从位置 strlen($string)/2 开始。然后，如果匹配成功，您将转到 strlen($string)/4、strlen($string)/8 等位置，直到不匹配为止，之后，您将检查当前位置之后的每个字符是否匹配。如果在位置 strlen($string)/2 处没有匹配项，则会在位置 strlen($string)-strlen($string)/2 进行检查，如果没有匹配项，则继续使用 strlen($string)-strlen($string)/4、strlen($string)-strlen($string)/8 等位置，直到匹配为止，然后向后一步进行检查。如果没有人尝试伪代码，我将使用 PHP。 - AndersTornkvist

Answer 3

在面试中我能想到的更简单的答案就是O(n^2)的解法，它尝试从0开始的所有子字符串组合。

int findSmallestUnit(string str){
    for(int i=1;i<str.length();i++){
        int j=0;
        for(;j<str.length();j++){
            if(str[j%i] != str[j]){
                break;
            }
        }
        if(j==str.length()) return str.substr(0,i);
    }
    return str;
}

现在如果有人对这个问题的O(n)解决方案感兴趣，可以使用c++：

  int findSmallestUnit(string str){
      vector<int> lps(str.length(),0);
      int i=1;
      int len=0;

      while(i<str.length()){
          if(str[i] == str[len]){
              len++;
              lps[i] = len;
              i++;
          }
          else{
              if(len == 0) i++;
              else{
                  len = lps[len-1];
              }
          }
      }
      int n=str.length();
      int x = lps[n-1];
      if(n%(n-x) == 0){
          return str.substr(0,n-x);    
      }
      return str;
  }

以上只是@Buge在C++中的回答，因为有人在评论中提问。

- Manish Madugula

Answer 4

O(n)解决方案。假设整个字符串必须被覆盖。关键观察是我们生成模式并测试它，但如果我们发现有些东西不匹配，我们必须包括我们已经测试过的整个字符串，这样我们就不必重新观察那些字符。

def pattern(inputv):
    pattern_end =0
    for j in range(pattern_end+1,len(inputv)):

        pattern_dex = j%(pattern_end+1)
        if(inputv[pattern_dex] != inputv[j]):

            pattern_end = j;
            continue

        if(j == len(inputv)-1):
            print pattern_end
            return inputv[0:pattern_end+1];
    return inputv;

- dfb

---

“for pattern_end in range(len(inputv)/2)” 这段代码必要吗？我认为不必要。 - Ishtar

@Ishtar - 抱歉我没听懂。你是指 len()/2 部分的外观吗？ - dfb

我的意思是，将那一行替换为 pattern_end = 0。 - Ishtar

很抱歉，该算法有误，请考虑输入："BCBDBCBCBDBC"。最小的重复模式是"BCBDBC"，但上述算法会忽略它。此外，我认为它在处理"HELLOHELL"的情况时也存在问题（它返回"HELLO"而不是完整字符串）。 - Eyal Schneider

@Boris：问题在于找到S的最小子序列，使得重复K>=1次会得到S本身。输入“HELLOHELL”没有重复子序列，K>1，因此应返回“HELLOHELL”。 - Eyal Schneider

Answer 5

Python中最简单的一个：

def pattern(self, s):
    ans=(s+s).find(s,1,-1)
    return len(pat) if ans == -1 else ans

- Pranav

---

如果您能解释一下您的做法，那将会很有帮助。 - thisisjaymehta

Answer 6

我的解决方案： 思路是从位置零开始找到一个子字符串，使其与相邻的同样长度的子字符串相等，当找到这样的子字符串时返回该子字符串。请注意，如果没有找到重复的子字符串，则打印整个输入字符串。

public static void repeatingSubstring(String input){
    for(int i=0;i<input.length();i++){
        if(i==input.length()-1){
            System.out.println("There is no repetition "+input);
        }
        else if(input.length()%(i+1)==0){
            int size = i+1;
            if(input.substring(0, i+1).equals(input.substring(i+1, i+1+size))){
                System.out.println("The subString which repeats itself is "+input.substring(0, i+1));
                break;
            }
        }
    }
}

- hdalali

---

我认为对于字符串 "ababcababc" 这个会失败。 - J.R.

Answer 7

我在您的帖子中找到了一个解决方案，可以处理不完整的模式：

(defn find-shortest-repeating [pattern string]
   (if (or (empty? (clojure.string/split string (re-pattern pattern)))
          (empty? (second (clojure.string/split string (re-pattern pattern)))))
    pattern
    (find-shortest-repeating (str pattern (nth string (count pattern))) string)))

- Alfonso Fernando Alvarez

---

@ward (defn find-pattern-string [string] (let [pattern "" working-str string] (reduce #(if (not (or (empty? (clojure.string/split string (re-pattern %1))) (empty? (second (clojure.string/split string (re-pattern %1)))))) (str %1 %2) %1) pattern working-str))) - Alfonso Fernando Alvarez

Answer 8

正则表达式解决方案：

使用以下正则表达式替换来查找最短重复子字符串，并仅保留该子字符串：

^(.+?)\1*$
$1

解释：

^(.+?)\1*$
^        $   # Start and end, to match the entire input-string
 (   )       # Capture group 1:
  .+         #  One or more characters,
    ?        #  with a reluctant instead of greedy match†
      \1*    # Followed by the first capture group repeated zero or more times

$1           # Replace the entire input-string with the first capture group match,
             # removing all other duplicated substrings

† 贪婪（Greedy） vs 懒惰（Reluctant）在这种情况下的含义是：贪婪模式 = 尽可能多地消耗字符；懒惰模式 = 尽可能少地消耗字符。由于我们想要最短的重复子字符串，所以我们需要在正则表达式中使用懒惰匹配。

示例输入："abkebabkebabkeb"
示例输出："abkeb"

在 Retina 中在线尝试。

这里是Java语言的一个实现示例。

- Kevin Cruijssen

---

这对于字符串 abaa 不起作用，期望的输出是 a。 - Himanshuman

如果我正确理解了问题，完整的单词始终由多个重复的子字符串构建而成，没有其他字符，因此 abab（2x ab）或 aaa（3x a）都是有效输入，但 abaa 不是（除非您将其视为 1x abaa）。@HimanshuPoddar - Kevin Cruijssen

哦，我的错，我混淆了问题，我正在阅读相似的问题。不过还是谢谢你的回复。 - Himanshuman

Answer 9

这是我使用队列想出的解决方案，它通过了Codeforces中一个类似问题的所有测试用例。问题编号为745A。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string s, s1, s2; cin >> s; queue<char> qu; qu.push(s[0]); bool flag = true; int ind = -1;
    s1 = s.substr(0, s.size() / 2);
    s2 = s.substr(s.size() / 2);
    if(s1 == s2)
    {
        for(int i=0; i<s1.size(); i++)
        {
            s += s1[i];
        }
    }
    //cout << s1 << " " << s2 << " " << s << "\n";
    for(int i=1; i<s.size(); i++)
    {
        if(qu.front() == s[i]) {qu.pop();}
        qu.push(s[i]);
    }
    int cycle = qu.size();

    /*queue<char> qu2 = qu; string str = "";
    while(!qu2.empty())
    {
        cout << qu2.front() << " ";
        str += qu2.front();
        qu2.pop();
    }*/


    while(!qu.empty())
    {
        if(s[++ind] != qu.front()) {flag = false; break;}
        qu.pop();
    }
    flag == true ? cout << cycle : cout << s.size();
    return 0;
}

- Sadman Sadeed Omee

Answer 10

我相信有一种非常优雅的递归解决方案。许多提出的解决方案解决了字符串以模式的一部分结尾的额外复杂性，例如abcabca。但我认为这不是要求的。

我在Clojure中提供了简单版本问题的解决方案：

 (defn find-shortest-repeating [pattern string]
  (if (empty? (str/replace string pattern ""))
   pattern
   (find-shortest-repeating (str pattern (nth string (count pattern))) string)))

(find-shortest-repeating "" "abcabcabc") ;; "abc"

但请注意，这将无法找到末尾不完整的模式。

- Ward