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

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

Ответ 1

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

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

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

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

Ответ 2

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

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

Ответ 3

Возможно, самый быстрый алгоритмический подход - это построение 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"));

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

Ответ 5

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

Ответ 6

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

Ответ 7

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

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

S: потенциальная длина допустимых подстрок

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

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

Ответ 8

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

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

Ответ 9

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

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

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

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

Ответ 10

Основная идея здесь состоит в том, чтобы исследовать любую потенциальную подстроку, начиная с длины 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

Ответ 11

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

Ответ 12

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

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