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

128

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

Махир Али
источник
19
Эта ссылка может быть вам полезна. Я всегда нахожу geekforgeeks хорошим источником проблем с алгоритмами - geeksforgeeks.org/…
Leron_says_get_back_Monica
9
Вы не возражаете, если я одолжу это и сделаю задачу кодирования на сайте обмена Programming Golf?
ouflak
7
@ouflak, ты можешь это сделать.
Махир Али
12
Если вам интересно, codegolf.stackexchange.com/questions/184682/…
ouflak
24
@Shidersz Использование нейронных сетей для этого немного похоже на стрельбу из пушки в комара.
JAD

Ответы:

186

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

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

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

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

templatetypedef
источник
13
Очень хорошо! Я добавил его на страницу тестирования jsPerf .
user42723
10
@ user42723 Круто! Похоже, это действительно очень быстро.
templatetypedef
5
К вашему сведению: мне было трудно поверить в это предложение, пока я не изменил формулировку: «Строка представляет собой нетривиальное вращение самой себя, если и только если она состоит из одного и того же шаблона, повторяемого несколько раз». Иди разбери.
Axel Podehl
11
У вас есть ссылки на эти теоремы?
HRK44,
4
Я думаю, что первое утверждение такое же, как « Лемма 2.3 : Если x и поворот x равны, то x является повторением» на doi.org/10.1016/j.tcs.2008.04.020 . См. Также: stackoverflow.com/a/2553533/1462295
BurnsBA
67

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

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

Pranav C Balan
источник
2
Не могли бы вы объяснить нам, что делает эта строка? Return /^(.+)\1+$/.test(str)
Thanveer Shah
34
И в чем сложность этого решения? Я не совсем уверен, но, похоже, он не намного быстрее, чем тот, который есть у OP.
Leron_says_get_back_Monica
8
@PranavCBalan Я плохо разбираюсь в алгоритмах, поэтому пишу в разделе комментариев. Однако у меня есть несколько вещей, которые следует упомянуть - у OP уже есть рабочее решение, поэтому он просит одно, которое даст ему лучшую производительность, а вы не объяснили, как ваше решение будет превосходить его. Короче не значит быстрее. Кроме того, из приведенной вами ссылки: If you use normal (TCS:no backreference, concatenation,alternation,Kleene star) regexp and regexp is already compiled then it's O(n).но, как вы писали, вы используете обратную ссылку, так что это все еще O (n)?
Leron_says_get_back_Monica
5
Вы можете использовать [\s\S]вместо, .если вам нужно сопоставить символы новой строки так же, как и другие символы. Символ точки не соответствует символам новой строки; альтернатива ищет все пробельные и непробельные символы, что означает, что в совпадение включаются символы новой строки. (Обратите внимание, что это быстрее, чем более интуитивно понятный (.|[\r\n]).) Однако, если строка определенно не содержит новых строк, тогда простой .будет самым быстрым. Обратите внимание, что это будет намного проще, если будет реализован флаг dotall .
HappyDog
2
Разве не /^(.+?)\1+$/немного быстрее? (12 шагов против 20 шагов)
онлайн Томас
29

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

MBO
источник
3
return z.some((zi, i) => (i + zi) === n && n % i === 0)
Pranav C Balan
2
Спасибо за добавление JavaScript в Салман А и Пранав С. Балан
MBo
1
Альтернативный подход, избегая дополнительной итерацииconst check = (s) => { let n = s.length; let z = Array(n).fill(0); for (let i = 1, l = 0, r = 0; i < n; ++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]; // check condition here and return if (z[i] + i === n && n % i === 0) return true; if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1; } // or return false return false; }
Пранав Балан
2
Использование z-функции - хорошая идея, но она «информационная», она содержит много информации, которая никогда не используется.
Axel Podehl
@Axel Podehl Тем не менее, он обрабатывает строку за O (n) раз (каждый символ используется не более двух раз). В любом случае мы должны проверять каждый char, поэтому теоретически более быстрого алгоритма не существует (хотя оптимизированные встроенные методы могут превзойти по производительности). Также в последней редакции я ограничил вычисление 1/2 длины строки.
MBo
23

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

user42723
источник
Это кажется очень быстрым, поскольку пропускает ненужные проверки.
Pranav C Balan
1
Очень хорошо, только я думаю, что перед вызовом подстроки проверю, повторяется ли первая буква в указанном месте.
Бен Фойгт
Для людей, впервые наткнувшихся на function*меня, как я, это объявление генератора, а не обычной функции. См. MDN
Жюльен Русе
17

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

gnasher729
источник
Я не проверял другие решения, но это кажется очень быстрым. Вы можете опустить часть «Если есть только один фактор N, отметьте ..., иначе» для простоты, так как это не особый случай. Было бы неплохо увидеть реализацию Javascript, которую можно запустить в jsPerf рядом с другими реализациями.
user42723
1
Я реализовал это в своем ответе
user42723
10

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

Аксель Подель
источник
1
Было бы быстрее проверить if( str===p.repeat(str.length/i) ) return true;вместо использования рекурсивной функции?
Chronocidal
1
Не помещайте console.logs в тесты jsperf, подготовьте функции в разделе глобальных переменных, а также подготовьте тестовые строки в разделе глобальных переменных (извините, не могу редактировать jsperf)
Салман А.
@ Салман - хорошее замечание. Я только что модифицировал jsperf своего предшественника (Pranav C), впервые использовал jsperf, классный инструмент.
Axel Podehl
@SalmanA: обновлено: jsperf.com/regex-and-loop/1 ... спасибо за информацию ... даже я с ней не знаком (Jsperf) ... спасибо за информацию
Пранав С. Балан,
Привет, Салман, большое спасибо за jsperf.com/reegx-and-loop/10 - да, этот новый тест производительности имеет гораздо больше смысла. Настройка функций должна идти в код подготовки.
Axel Podehl
7

Написал это на 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")
JustABeginner
источник
6

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

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

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

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

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

SunKnight0
источник
5

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

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

Пер Александерссон
источник
4

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

Остин Маллинз
источник
-1

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

infmagic2047
источник
ОП хочет знать, существует ли повторение . Вторая строка (тела) вашей функции подсчитывает количество повторений - это бит, который необходимо объяснить. Например, «abcabcabc» имеет 3 повторения «abc», но как ваша вторая строка сработала, есть ли в ней какие-либо повторы?
Лоуренс
@ Лоуренс, я не понимаю вашего вопроса. Этот алгоритм основан на идее о том , что строка является повторением ее подстроки , если и только если для некоторого делителя ее длины i, s[0:n-i] == s[i:n]или , что эквивалентно, s == s[i:n] + s[0:i]. Зачем второй строке нужно выяснять, были ли в ней повторы?
infmagic2047
Посмотрим, понимаю ли я ваш алгоритм. Сначала вы присоединяете strсебя к форме t, затем просматриваете, tчтобы попытаться найти strвнутри t. Хорошо, это может сработать (я отозвал свой голос против). Однако это не линейно в strlen (str). Say strимеет длину L. Затем в каждой позиции p = 0,1,2, ..., проверяя, принимает ли str [0..L-1] == t [p..p + L-1] значение O (L ) время. Вам нужно выполнять проверки O (L), когда вы просматриваете значения p, поэтому это O (L ^ 2).
Лоуренс
-10

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

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

Винод Кумар Г
источник
да, для abc или unicorn пользователь не будет проверять с помощью / abc / или / unicorn /, извините, если мне не хватает вашего контекста
Винод Кумар G
3
Вопрос мог бы быть более ясным, но то, что он просит, - это способ решить, состоит ли строка полностью из 2 или более повторений любой другой строки. Он не ищет конкретную подстроку.
HappyDog
2
Я добавил некоторые пояснения к вопросу, которые теперь должны прояснить его.
HappyDog
@Vinod, если вы уже собираетесь использовать регулярное выражение, вы должны привязать совпадение и использовать test. Нет причин изменять строку только для проверки какого-либо условия.
Мари