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

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

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

Answer 2

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

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