Нахождение кратчайшего повторяющегося цикла в слове?

Question

Я собираюсь написать функцию, которая выдаст мне кратчайший период группы букв, который в конечном итоге создаст данное слово.

Например, слово abkebabkebabkeb создается повторяющимся словом abkeb . Хотелось бы узнать, насколько эффективно анализировать входное слово, чтобы получить кратчайший период для символов, создающих входное слово.

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]

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

Answer 3

O (n) раствор. Предполагается, что вся строка должна быть покрыта. Ключевое наблюдение заключается в том, что мы генерируем шаблон и тестируем его, но если мы находим что-то по пути, которое не соответствует, мы должны включить всю строку, которую мы уже тестировали, чтобы нам не пришлось заново наблюдать эти символы. 1001 *

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;

Answer 4

Регулярное решение:

Шаг 1: Разделите каждый символ символом-разделителем, который не является частью строки ввода, включая завершающий (т. Е. ~):

(.)
$1~

Пример ввода: "abkebabkebabkeb"
Пример вывода: "a~b~k~e~b~a~b~k~e~b~a~b~k~e~b~"

Попробуйте онлайн в Retina. ( ПРИМЕЧАНИЕ: Retina - это язык программирования на основе регулярных выражений, разработанный для быстрого тестирования регулярных выражений и способный успешно конкурировать в вызовы для игры в гольф . )

Шаг 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.

Answer 5

Мое решение: Идея состоит в том, чтобы найти подстроку с нулевой позиции так, чтобы она стала равной смежной подстроке такой же длины, когда такая подстрока найдена и возвращает подстроку. Обратите внимание: если повторяющаяся подстрока не найдена, я печатаю всю введенную строку.

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

Answer 6

Я нашел решение, основанное на вашем посте, которое могло бы принять неполный шаблон:

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

Answer 7

Я считаю, что есть очень элегантное рекурсивное решение.Многие из предложенных решений решают дополнительную сложность, когда строка заканчивается частью шаблона, например 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"

Но имейте в виду, что это не приведет к обнаружению неполных шаблонов приконец.

Answer 8

Я придумал простое решение, которое безупречно работает даже с очень большими строками.
Реализация 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;
}

Answer 9

Работает в таких случаях, как 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;
}

Answer 10

Супер отложенный ответ, но я получил вопрос в интервью, вот мой ответ (вероятно, не самый оптимальный, но он работает и для странных тестовых случаев).

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

Testcases:

abcabcabcabc
bcbcbcbcbcbcbcbcbcbcbcbcbcbc
dddddddddddddddddddd
adcdefg
bcbdbcbcbdbc
привет

Код возвращается:

а
до н.э.
д
adcdefg
bcbdbc
hellohell