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

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;

纤洞需匪

这是一个正确的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]

剑哎

这是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;
}
?>

蜂佬渺

我相信有一个非常优雅的递归解决方案。许多建议的解决方案解决了字符串以部分模式结尾（如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\"

但是请注意，这将不会找到最后不完整的模式。

炉挤仙挟

我根据您的帖子找到了一个解决方案，该解决方案可能采用不完整的模式：

(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)))

靛取糕奖穿

我的解决方案：这个想法是从零位置找到一个子串，以使其等于相同长度的相邻子串，当找到这样的子串时，返回该子串。请注意，如果找不到重复的子字符串，我将打印整个输入字符串。

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

物崎巩

正则表达式解决方案：第1步：使用不属于输入字符串的定界字符分隔每个字符，包括结尾的字符（即~）：

(.)
$1~

输入示例：\"abkebabkebabkeb\" 输出示例：\"a~b~k~e~b~a~b~k~e~b~a~b~k~e~b~\" 在Retina上在线尝试。（注意：Retina是一种基于Regex的编程语言，旨在快速测试regexes并能够成功地应对代码高尔夫挑战。）步骤2：使用以下正则表达式查找最短的重复子字符串（其中~是我们选择的定界符）：

^(([^~]+~)*?)\\1*$
$1

说明：

^(([^~]+~)*?)\\1*$
^               $    # Start and end, to match the entire input-string
  ([^~]+~)           # Capture group 1: One or more non-\'~\' followed by a \'~\'
 (        *?)        # Capture group 2: Repeated zero or more time optionally
             \\1*     # Followed by the first capture group repeated zero or more times

$1                   # Replace the entire input-string with the first capture group match

输入示例：\"a~b~k~e~b~a~b~k~e~b~a~b~k~e~b~\" 输出示例：\"a~b~k~e~b~\" 在Retina上在线尝试。步骤3：再次删除定界符，以获得预期的结果。

~
<empty>

输入示例：\"a~b~k~e~b~\" 输出示例：\"abkeb\" 在Retina上在线尝试。这里是Java的示例实现。

辽躺

超级延迟的答案，但我在一次采访中遇到了问题，这是我的答案（可能不是最佳答案，但它也适用于奇怪的测试用例）。

private void run(String[] args) throws IOException {
    File file = new File(args[0]);
    BufferedReader buffer = new BufferedReader(new FileReader(file));
    String line;
    while ((line = buffer.readLine()) != null) {
        ArrayList<String> subs = new ArrayList<>();
        String t = line.trim();
        String out = null;
        for (int i = 0; i < t.length(); i++) {
            if (t.substring(0, t.length() - (i + 1)).equals(t.substring(i + 1, t.length()))) {
                subs.add(t.substring(0, t.length() - (i + 1)));
            }
        }
        subs.add(0, t);
        for (int j = subs.size() - 2; j >= 0; j--) {
            String match = subs.get(j);
            int mLength = match.length();
            if (j != 0 && mLength <= t.length() / 2) {
                if (t.substring(mLength, mLength * 2).equals(match)) {
                    out = match;
                    break;
                }
            } else {
                out = match;
            }
        }
        System.out.println(out);
    }
}

测试用例： abcabcabcabc bcbcbcbcbcbcbcbcbcbcbcbcbcbc dddddddddddddddddddddd adcdefg bcbdbcbcbdbc 你好代码返回： abc 公元前 d adcdefg bcbdbc 你好

蹦吃舷弦

在bcbdbcbcbdbc之类的情况下有效。

function smallestRepeatingString(sequence){
  var currentRepeat = \'\';
  var currentRepeatPos = 0;

  for(var i=0, ii=sequence.length; i<ii; i++){
    if(currentRepeat[currentRepeatPos] !== sequence[i]){
      currentRepeatPos = 0;
      // Add next character available to the repeat and reset i so we don\'t miss any matches inbetween
      currentRepeat = currentRepeat + sequence.slice(currentRepeat.length, currentRepeat.length+1);
      i = currentRepeat.length-1;
    }else{
      currentRepeatPos++;
    }
    if(currentRepeatPos === currentRepeat.length){
      currentRepeatPos = 0;
    }
  }

  // If repeat wasn\'t reset then we didn\'t find a full repeat at the end.
  if(currentRepeatPos !== 0){ return sequence; }

  return currentRepeat;
}

钨蜡唤喉晤

我想出了一个简单的解决方案，即使使用非常大的字符串也可以完美地工作。 PHP实现：

function get_srs($s){
    $hash = md5( $s );
    $i = 0; $p = \'\';

    do {
        $p .= $s[$i++];
        preg_match_all( \"/{$p}/\", $s, $m );
    } while ( ! hash_equals( $hash, md5( implode( \'\', $m[0] ) ) ) );

    return $p;
}

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

10 个回复

发起人

pseudocode

algorithm

language_agnostic

问题状态

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

与内容相关的链接

10 个回复

发起人

pseudocode

algorithm

language_agnostic

问题状态