Ответ 1

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;

Ответ 2

Вот правильный алгоритм 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]

Ответ 3

Это пример для 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;
}
?>

Ответ 4

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

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

Ответ 5

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

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

Ответ 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;
            }
        }
    }
}

Ответ 7

Regex решение:

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

(.)
$1~

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

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

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

Ответ 8

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

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
hellohell

Возврат кода:

а
Ьс
d
adcdefg
bcbdbc
hellohell

Ответ 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;
}

Ответ 10

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