logo标签列表

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

algorithmlanguage-agnosticpseudocode
23
我将要编写一个函数，它将返回一个最短周期的字母组合，这个组合最终可以创建给定的单词。
例如，单词abkebabkebabkeb是由重复的abkeb单词创建的。我想知道如何高效地分析输入的单词，以获取创建输入单词的最短字符周期。
@Tony The Tiger，结果（最短时间）不必是一个真实的单词。 - jack44
13个回答
-1

我想出了一个简单的解决方案，即使在非常大的字符串下也能完美运行。
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;
}
1
如果您能详细说明为什么这个方法有效，那就更好了。提供更多细节有助于整个社区，并有助于获得更多的赞同票。 - Charlie Fish
-1

适用于 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;
}
1
这实际上是O(n^2)。这是因为您使用i = currentRepeat.length-1;将i重置为较小的值。因此，对于一个包含10个字符的字符串'aaaaaaaaab'，需要46次迭代。对于一个包含20个字符的字符串，需要191次迭代。 - Buge
-1

非常抱歉回答晚了，但我在面试中得到了这个问题，以下是我的答案（可能不是最优的，但它也适用于奇怪的测试用例）。

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
dddddddddddddddddddd
adcdefg
bcbdbcbcbdbc
hellohell

代码返回：

abc
bc
d
adcdefg
bcbdbc
hellohell

1
仅就第一个for循环而言，其时间复杂度为O(n^2)，因为每个.equals()操作都可能需要n的时间。 - Buge
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接