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

Question

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

Answer 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 - длина входной строки.

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

Answer 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

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

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

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

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

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

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

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

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

Answer 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 символов.

Answer 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

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

Answer 7

Написал это на Python. Я знаю, что это не платформа, но это заняло 30 минут времени. P.S. => 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")

Answer 8

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

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

S: Потенциальные длины действительных подстрок

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

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

Answer 9

Следующий код 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.

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

Answer 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