Как проверить, полностью ли строка состоит из одной и той же подстроки?

Мне нужно создать функцию, которая принимает строку, и она должна возвращать 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)

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

function check(str){
  if(!(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"),''))
    if(!str.replace(new RegExp(temp,"g"),'')) return true;
  }
  return false;
}

console.log(check('aa')) //true
console.log(check('aaa')) //true
console.log(check('abcabcabc')) //true
console.log(check('aba')) //false
console.log(check('ababa')) //false

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

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

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

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

Здесь поворот означает удаление некоторого количества символов из передней части строки и перемещение их назад. Например, строку 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;
}

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

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

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

function check(str) {
  return /^(.+)\1+$/.test(str)
}

console.log(check('aa')) //true
console.log(check('aaa')) //true
console.log(check('abcabcabc')) //true
console.log(check('aba')) //false
console.log(check('ababa')) //false

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

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

Объяснение регулярного выражения здесь

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

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

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

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

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

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

vector<int> z_function(string s) {
    int n = (int) s.length();
    vector<int> 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;
  //for our task we need only a half of z-array
  for (i = 1, l = 0, r = 0; i <= n/2; ++i) {
    if (i <= r)
      z[i] = Math.min(r - i + 1, z[i - l]);
    while (i + z[i] < n && s[z[i]] == s[i + z[i]])
      ++z[i];

      //we can check condition and return here
     if (z[i] + i === n && n % i === 0) return true;
    
    if (i + z[i] - 1 > r)
      l = i, r = i + z[i] - 1;
  }
  return false; 
  //return 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и можно будет вернуться true.

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

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, повторяемая три раза.

Прочитал ответ 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<p; j++) {
            if (s != str.substring(l*j, l*(j+1))) continue primeloop
        }
        return true
    }
    return false
}

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

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, которая содержит алгоритмы, используемые на этой странице.

Предположим, что строка 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, делящих длина S.

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

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

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

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

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

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

function check(str)
{
  if( str.length==1 ) return true; // trivial case
  for( var i=1;i<=str.length/2;i++ ) { // biggest possible repeated pattern has length/2 characters

    if( str.length%i!=0 ) continue; // pattern of size i doesn't fit
    
    var p = str.substring(0, i);
    if( isRepeating(p,str) ) return true;
  }
  return false;
}


function isRepeating(p, str)
{
  if( str.length>p.length ) { // maybe more than 2 occurences

    var left = str.substring(0,p.length);
    var right = str.substring(p.length, str.length);
    return left===p && isRepeating(p,right);
  }
  return str===p; 
}

console.log(check('aa')) //true
console.log(check('aaa')) //true 
console.log(check('abcabcabc')) //true
console.log(check('aba')) //false
console.log(check('ababa')) //false

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

Написал это на Python. Я знаю, что это не платформа, но это заняло 30 минут. PS => PYTHON

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

Мой подход похож на gnasher729 в ​​том, что он использует потенциальную длину подстроки в качестве основного фокуса, но он менее математичен и требует больших усилий:

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

S: возможные длины допустимых подстрок

Выполните цикл S от (целой части) L / 2 до 1. Если L / S является целым числом, проверьте исходную строку на соответствие первым S-символам исходной строки, повторенным L / S раз.

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

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

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

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

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

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

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

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

function check(str) {
  const len = str.length;
  for (let subl = 1; subl <= len/2; ++subl) {
    if ((len % subl != 0) || str[0] != str[subl])
      continue;
    
    let i = 1;
    for (; i < subl; ++i)
    {
      let j = 0;
      for (; j < len; j += subl)
        if (str[i] != str[j + i])
          break;
      if (j != len)
        break;
    }
    
    if (i == subl)
      return true;
  }
  return false;
}

console.log(check('aa')) //true
console.log(check('aaa')) //true
console.log(check('abcabcabc')) //true
console.log(check('aba')) //false
console.log(check('ababa')) //false

Я не знаком с 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.

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

'ababababa'.replace(/ab/gi,'')
"a" // return false
'abababab'.replace(/ab/gi,'')
 ""// return true