Мне нужно создать функцию, которая принимает строку, и она должна возвращать true или false в зависимости от того, состоит ли ввод из повторяющейся последовательности символов. Длина данной строки всегда больше, чем 1, и последовательность символов должна иметь хотя бы одно повторение.

"aa" // true(entirely contains two strings "a")
"aaa" //true(entirely contains three string "a")
"abcabcabc" //true(entirely containas three strings "abc")

"aba" //false(At least there should be two same substrings and nothing more)
"ababa" //false("ab" exists twice but "a" is extra so false)

Я создал следующую функцию:

проверка работы (str) {
  если (! (str.length && str.length - 1)) return false;
  let temp = '';
  for (let i = 0; i <= str.length / 2; i ++) {
    temp + = str [i]
    //console.log(str.replace(new RegExp (temp, "g"), ''))
    если (! str.replace (new RegExp (temp, "g"), '')) return true;
  }
  вернуть ложь;
}

console.log (check ('aa')) // правда
console.log (check ('aaa')) // правда
console.log (check ('abcabcabc')) // правда
console.log (check ('aba')) // ложь
console.log (check ('ababa')) // ложь

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

Вторая проблема заключается в том, что он использует replace () в каждом цикле, что замедляет его работу. Есть ли лучшее решение по производительности?

Maheer Ali

Ответов: 13

Ответы (13)

Есть отличная маленькая теорема о таких строках.

Строка состоит из одного и того же шаблона, повторяемого несколько раз тогда и только тогда, когда строка представляет собой нетривиальное вращение самой себя.

Здесь поворот означает удаление некоторого количества символов из передней части строки и перемещение их в конец. Например, строка hello может быть повернута для образования любой из этих строк:

hello (the trivial rotation)
elloh 
llohe 
lohel 
ohell 

Чтобы понять, почему это работает, сначала предположим, что строка состоит из k повторяющихся копий строки w. Затем, если удалить первую копию повторяющегося рисунка (w) с лицевой стороны струны и прикрепить ее к оборотной стороне, получится та же самая струна. Обратное направление немного сложнее доказать, но идея заключается в том, что если вы повернете строку и вернетесь к тому, с чего начали, вы можете многократно применить это вращение, чтобы выложить строку несколькими копиями одного и того же шаблона (этот шаблон является строка, которую нужно было переместить в конец, чтобы выполнить поворот).

Теперь вопрос, как проверить, так ли это. Для этого можно использовать еще одну прекрасную теорему:

Если x и y - строки одинаковой длины, то x - это поворот y тогда и только тогда, когда x является подстрокой yy.

В качестве примера мы видим, что lohel - это вращение hello следующим образом:

hellohello
   ^^^^^

В нашем случае мы знаем, что каждая строка x всегда будет подстрокой xx (она будет появляться дважды, по одному разу в каждой копии x). Итак, в основном нам просто нужно проверить, является ли наша строка x подстрокой xx, не позволяя ей совпадать с первым или половинным символом. Вот краткое описание этого:

function check(str) {
    return (str + str).indexOf(str, 1) !== str.length;
}

Assuming indexOf is implemented using a fast string matching algorithm, this will run in time O(n), where n is the length of the input string.

Надеюсь, это поможет!

Одна из простых идей состоит в том, чтобы заменить строку подстрокой "", и если какой-либо текст существует, то он ложен, иначе это правда.

'ababababa'.replace (/ ab / gi,' ')
"а" // вернуть ложь
'abababab'.replace (/ ab / gi,' ')
 "" // вернем истину

Вы можете сделать это с помощью группы захвата и обратной ссылки. Просто проверьте, что это повтор первого захваченного значения.

проверка работы (str) {
  возврат /^(.+)\1+$/.test(str)
}

console.log (check ('aa')) // правда
console.log (check ('aaa')) // правда
console.log (check ('abcabcabc')) // правда
console.log (check ('aba')) // ложь
console.log (check ('ababa')) // ложь

В приведенном выше RegExp:

  1. ^ и $ обозначает начало и конец привязки для прогнозирования позиции.
  2. (. +) захватывает любой шаблон и фиксирует значение (кроме \ n).
  3. \ 1 - это обратная ссылка на первое захваченное значение, а \ 1 + будет проверять повторение захваченного значения.

Объяснение Regex здесь

Для отладки RegExp используйте: https://regex101.com/r/pqlAuP/1/debugger

Производительность: https://jsperf.com/reegx-and-loop/13

Прочитал ответ gnasher729 и реализовал. Идея состоит в том, что если есть какие-то повторы, то должно быть (также) простое количество повторов.

function* primeFactors (n) {
    for (var k = 2; k*k <= n; k++) {
        if (n % k == 0) {
            yield k
            do {n /= k} while (n % k == 0)
        }
    }
    if (n > 1) yield n
}

function check (str) {
    var n = str.length
    primeloop:
    for (var p of primeFactors(n)) {
        var l = n/p
        var s = str.substring(0, l)
        for (var j=1; j

Немного другой алгоритм:

function check (str) {
    var n = str.length
    for (var p of primeFactors(n)) {
        var l = n/p
        if (str.substring(0, n-l) == str.substring(l)) return true
    }
    return false
}

Я обновил страницу jsPerf, которая содержит алгоритмы, используемые на этой странице.

Написал это на Python. Я знаю, что это не платформа, но это заняло 30 минут. P.S. => ПИТОН

def checkString(string):
    gap = 1 
    index= 0
    while index < len(string)/2:
        value  = [string[i:i+gap] for i in range(0,len(string),gap) ]

        x = [string[:gap]==eachVal for eachVal in value]

        if all(x):
            print("THEY ARE  EQUAL")
            break 

        gap = gap+1
        index= index+1 

checkString("aaeaaeaaeaae")

Прошло больше года с тех пор, как этот вопрос был опубликован, но я использовал длину строки и форму объекта, чтобы проверить, истинно оно или ложно.

const check = (str) => {
  пусть count = 0;
  let obj = {};
  если (str.length <2) вернуть false;
  
  for (let i = 0; i  item === 1)) {
    вернуть ложь
  };
  
  if ([... str] .length% count === 0) {
    вернуть истину
  } еще {
    вернуть ложь
  };
};

console.log (check ("abcabcabcac")) // ложь
console.log (check ("aaa")) // верно
console.log (check ("acaca")) // ложь
console.log (check ("aa")) // правда
console.log (check ("abc")) // ложь
console.log (check ("aabc")) // ложь

Следующий код в системе Mathematica почти определяет, повторяется ли список хотя бы один раз. Если строка повторяется хотя бы один раз, возвращается истина, но он также может вернуть истину, если строка представляет собой линейную комбинацию повторяющихся строк.

IsRepeatedQ[list_] := Module[{n = Length@list},
   Round@N@Sum[list[[i]] Exp[2 Pi I i/n], {i, n}] == 0
];

Этот код ищет "полноразмерный" вклад, который должен быть равен нулю в повторяющейся строке, но строка accbbd также считается повторяющейся, поскольку это сумма двух повторяющихся строк ababab и 012012.

Идея состоит в том, чтобы использовать быстрое преобразование Фурье и искать частотные спектры. Посмотрев на другие частоты, можно будет обнаружить и этот странный сценарий.

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

function check(str) {
    t = str + str;
    find all overlapping occurrences of str in t;
    for each occurrence at position i
        if (i > 0 && i < str.length && str.length % i == 0)
            return true;  // str is a repetition of its first i characters
    return false;
}

Идея аналогична ответу MBo. Для каждого i, который делит длину, str является повторением его первых i символов тогда и только тогда, когда он остается таким же после сдвига на i. знаков.

Мне приходит в голову, что такая встроенная функция может быть недоступна или неэффективна. В этом случае всегда можно реализовать алгоритм KMP вручную, что требует примерно того же количества кода, что и алгоритм в ответе MBo.

Предположим, что строка S имеет длину N и состоит из дубликатов подстроки s, тогда длина s делит N. Например, если S имеет длину 15, то подстрока имеет длину 1, 3 или 5.

Пусть S состоит из (p * q) копий s. Тогда S также состоит из p копий (s, повторяется q раз). Таким образом, у нас есть два случая: если N - простое число или 1, то S может состоять только из копий подстроки длины 1. Если N составное, то нам нужно только проверить подстроки s длины N / p на наличие простых чисел p, делящих длина С.

Итак, определите N = длина S, а затем найдите все его простые множители за время O (sqrt (N)). Если есть только один множитель N, проверьте, является ли S одной и той же строкой, повторенной N раз, в противном случае для каждого простого множителя p проверьте, состоит ли S из p повторений первых N / p символов.

Основная идея здесь состоит в том, чтобы исследовать любую потенциальную подстроку, начиная с длины 1 и заканчивая половиной длины исходной строки. Мы смотрим только на длину подстроки, которая равномерно делит исходную длину строки (т.е. str.length% substring.length == 0).

Эта реализация просматривает первый символ каждой возможной итерации подстроки перед переходом ко второму символу, что может сэкономить время, если предполагается, что подстроки будут длинными. Если после проверки всей подстроки несоответствия не обнаружено, мы возвращаем true.

Мы возвращаем false, когда у нас заканчиваются потенциальные подстроки для проверки.

проверка работы (str) {
  const len ​​= длина строки;
  for (let subl = 1; subl <= len / 2; ++ subl) {
    если ((len% subl! = 0) || str [0]! = str [subl])
      Продолжать;
    
    пусть i = 1;
    для (; я 

Возможно, самый быстрый алгоритмический подход - это построение Z-функции за линейное время:

Z-функция для этой строки представляет собой массив длины n, где i-й элемент равен наибольшему количеству символов, начиная с позиция i, совпадающая с первыми символами s.

Другими словами, z [i] - это длина самого длинного общего префикса. между s и суффиксом s, начиная с i.

Реализация C ++ для справки:

vector z_function(string s) {
    int n = (int) s.length();
    vector z(n);
    for (int i = 1, l = 0, r = 0; i < n; ++i) {
        if (i <= r)
            z[i] = min (r - i + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
            ++z[i];
        if (i + z[i] - 1 > r)
            l = i, r = i + z[i] - 1;
    }
    return z;
}

реализация JavaScript
Добавлены оптимизации - построение половины z-массива и ранний выход

function z_function (s) {
  var n = s.length;
  var z = Array (n) .fill (0);
  var i, l, r;
  // для нашей задачи нам понадобится только половина z-массива
  for (i = 1, l = 0, r = 0; i <= n / 2; ++ i) {
    если (я <= г)
      z [i] = Math.min (r - i + 1, z [i - l]);
    в то время как (i + z [i]  r)
      l = i, r = i + z [i] - 1;
  }
  вернуть ложь;
  // вернуть z.some ((zi, i) => (i + zi) === n && n% i === 0);
}
console.log (z_function ("abacabacabac"));
console.log (z_function ("abcab"));

Затем вам нужно проверить индексы i, которые делят n. Если вы найдете такой i, что i + z [i] = n, тогда строка s может быть сжата до длины i и можно вернуть истина.

Например, для

string s= 'abacabacabac'  with length n=12`

z-массив

(0, 0, 1, 0, 8, 0, 1, 0, 4, 0, 1, 0)

и мы можем найти это для

i=4
i+z[i] = 4 + 8 = 12 = n
and
n % i = 12 % 4 = 0`

, поэтому s можно представить как подстроку длины 4, повторяющуюся три раза.

Я думаю, что рекурсивная функция тоже может быть очень быстрой. Первое наблюдение заключается в том, что максимальная длина повторяющегося шаблона составляет половину длины всей строки. И мы могли бы просто протестировать все возможные длины повторяющихся паттернов: 1, 2, 3, ..., str.length / 2

Рекурсивная функция isRepeating (p, str) проверяет, повторяется ли этот шаблон в str.

Если str длиннее шаблона, рекурсия требует, чтобы первая часть (такой же длины, как p) была повторением, а также оставшаяся часть str. Таким образом, str эффективно разбивается на части длиной p.length.

Если тестируемый шаблон и str имеют одинаковый размер, рекурсия здесь успешно завершается.

Если длина отличается (происходит для «aba» и шаблона «ab») или если части разные, то возвращается false, распространяясь вверх по рекурсии.

проверка работы (str)
{
  если (str.length == 1) вернуть истину; // тривиальный случай
  for (var i = 1; i <= str.length / 2; i ++) {// максимально возможный повторяющийся шаблон имеет длину / 2 символа

    если (длина строки% i! = 0) продолжить; // шаблон размера i не подходит
    
    var p = str.substring (0, i);
    если (isRepeating (p, str)) вернуть истину;
  }
  вернуть ложь;
}


функция isRepeating (p, str)
{
  if (str.length> p.length) {// может быть больше двух вхождений

    var left = str.substring (0, длина строчки);
    var right = str.substring (p.length, str.length);
    return left === p && isRepeating (p, right);
  }
  return str === p;
}

console.log (check ('aa')) // правда
console.log (check ('aaa')) // правда
console.log (check ('abcabcabc')) // правда
console.log (check ('aba')) // ложь
console.log (check ('ababa')) // ложь

Производительность: https://jsperf.com/reegx-and-loop/13

• 100001

L: длина исходной строки

S: Возможная длина допустимых подстрок

Loop S from (integer part of) L/2 to 1. If L/S is an integer check your original string against the fist S characters of the original string repeated L/S times.

Причина зацикливания от L / 2 назад, а не от 1 вперед, состоит в том, чтобы получить максимально возможную подстроку. Если вам нужен наименьший возможный цикл подстроки от 1 до L / 2. Пример: «abababab» имеет как «ab», так и «abab» в качестве возможных подстрок. Какой из двух будет быстрее, если вас интересует только истинный / ложный результат, зависит от типа строк / подстрок, к которым они будут применены.

2022 WebDevInsider