Como verifico se uma string é totalmente composta da mesma substring?

Eu tenho que criar uma função que aceita uma string e ela deve retornar trueou com falsebase em se a entrada consiste em uma sequência de caracteres repetida. O comprimento da sequência especificada é sempre maior que 1e a sequência de caracteres deve ter pelo menos uma repetição.

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

Eu criei a função abaixo:

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

A verificação disso faz parte do problema real. Não posso pagar uma solução não eficiente como essa. Primeiro de tudo, ele passa pela metade da corda.

O segundo problema é que ele está usando replace()em cada loop, o que o torna lento. Existe uma solução melhor em relação ao desempenho?

Existe um teorema bacana sobre cordas como essas.

Uma sequência consiste no mesmo padrão repetido várias vezes se e somente se a sequência for uma rotação não trivial de si mesma.

Aqui, uma rotação significa excluir um número de caracteres da frente da string e movê-los para trás. Por exemplo, a string hellopode ser girada para formar qualquer uma dessas strings:

hello (the trivial rotation)
elloh 
llohe 
lohel 
ohell 

Para ver por que isso funciona, primeiro, suponha que uma string consista em k cópias repetidas de uma string w. Em seguida, excluir a primeira cópia do padrão repetido (w) da frente da corda e prendê-la na parte de trás dará a mesma sequência. A direção reversa é um pouco mais difícil de provar, mas a idéia é que, se você girar uma sequência e voltar com o que começou, poderá aplicar essa rotação repetidamente para agrupar a sequência com várias cópias do mesmo padrão (esse padrão é o você precisa ir até o final para fazer a rotação).

Agora, a questão é como verificar se esse é o caso. Para isso, há outro belo teorema que podemos usar:

Se xey são cadeias de caracteres do mesmo comprimento, x é uma rotação de y se e somente se x é uma subcadeia de yy.

Como exemplo, podemos ver que lohelé uma rotação da helloseguinte maneira:

hellohello
   ^^^^^

No nosso caso, sabemos que toda string x sempre será uma subcadeia de xx (aparecerá duas vezes, uma vez em cada cópia de x). Então, basicamente, precisamos apenas verificar se nossa string x é uma subcadeia de xx sem permitir que ela corresponda no primeiro caractere ou na metade do caminho. Aqui está uma linha para isso:

function check(str) {
    return (str + str).indexOf(str, 1) !== str.length;
}

Supondo que indexOfseja implementado usando um algoritmo de correspondência rápida de strings, ele será executado no tempo O (n), em que n é o comprimento da string de entrada.

Espero que isto ajude!

Você pode fazê-lo por um grupo de captura e backreference . Basta verificar se é a repetição do primeiro valor capturado.

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

No RegExp acima:

1. ^e $significa âncoras de início e fim para prever a posição.
2. (.+)captura qualquer padrão e captura o valor (exceto \n).
3. \1é uma referência anterior ao primeiro valor capturado e \1+verificaria a repetição do valor capturado.

Explicação Regex aqui

Para a depuração do RegExp, use: https://regex101.com/r/pqlAuP/1/debugger

Desempenho: https://jsperf.com/reegx-and-loop/13

Talvez a abordagem algorítmica mais rápida seja a construção de uma função Z em tempo linear:

A função Z para essa string é uma matriz de comprimento n, em que o i-ésimo elemento é igual ao maior número de caracteres começando na posição i que coincide com os primeiros caracteres de s.

Em outras palavras, z [i] é o comprimento do maior prefixo comum entre se o sufixo de s começa em i.

Implementação C ++ para referência:

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;
}

Implementação de JavaScript
Otimizações adicionadas - criação de metade do z-array e saída antecipada

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

Então você precisa verificar índices ique dividem n. Se você achar ique isso i+z[i]=n, a sequência spoderá ser compactada no comprimento ie você poderá retornar true.

Por exemplo, para

string s= 'abacabacabac'  with length n=12`

matriz z é

(0, 0, 1, 0, 8, 0, 1, 0, 4, 0, 1, 0)

e podemos encontrar isso para

i=4
i+z[i] = 4 + 8 = 12 = n
and
n % i = 12 % 4 = 0`

portanto, spode ser representado como substring de comprimento 4 repetido três vezes.

Eu li a resposta de gnasher729 e a implementei. A idéia é que, se houver repetições, deve haver (também) um número primo de repetições.

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
}

Um algoritmo ligeiramente diferente é o seguinte:

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
}

Atualizei a página jsPerf que contém os algoritmos usados ​​nesta página.

Suponha que a sequência S tenha comprimento N e seja feita de duplicatas da substring s, então o comprimento de s divide N. Por exemplo, se S tiver comprimento 15, a substring terá comprimento 1, 3 ou 5.

Seja S feito de (p * q) cópias de s. Então S também é feito de p cópias de (s, repetidas q vezes). Temos, portanto, dois casos: se N é primo ou 1, então S pode ser feito apenas de cópias da substring de comprimento 1. Se N é composto, precisamos apenas verificar substrings s de comprimento N / p para primos p divididos o comprimento de S.

Portanto, determine N = o comprimento de S e encontre todos os fatores primos no tempo O (sqrt (N)). Se houver apenas um fator N, verifique se S é a mesma sequência repetida N vezes, caso contrário, para cada fator primo p, verifique se S consiste em repetições de p dos primeiros caracteres N / p.

Eu acho que uma função recursiva pode ser muito rápida também. A primeira observação é que o comprimento máximo repetido do padrão é metade do comprimento da string total. E poderíamos testar todos os possíveis comprimentos repetidos de padrões: 1, 2, 3, ..., str.length / 2

A função recursiva isRepeating (p, str) testa se esse padrão é repetido em str.

Se str for maior que o padrão, a recursão exige que a primeira parte (mesmo comprimento que p) seja uma repetição, bem como o restante de str. Então, str é efetivamente dividido em pedaços de comprimento p.length.

Se o padrão e str testados tiverem o mesmo tamanho, a recursão termina aqui com êxito.

Se o comprimento for diferente (acontece para "aba" e padrão "ab") ou se as peças forem diferentes, falso será retornado, propagando a recursão.

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

Desempenho: https://jsperf.com/reegx-and-loop/13

Escreveu isso em Python. Eu sei que não é a plataforma, mas demorou 30 minutos. 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")

Minha abordagem é semelhante ao gnasher729, na medida em que usa o comprimento potencial da substring como foco principal, mas é menos matemático e intensivo em processos:

L: Comprimento da corda original

S: Comprimentos potenciais de sub-strings válidas

Loop S de (parte inteira de) L / 2 a 1. Se L / S for um número inteiro, verifique sua string original com os primeiros caracteres S da string original repetidos vezes L / S.

O motivo do loop de L / 2 para trás e não de 1 em diante é obter a maior substring possível. Se você deseja o menor loop de substring possível de 1 a L / 2. Exemplo: "abababab" possui "ab" e "abab" como possíveis substrings. Qual dos dois seria mais rápido se você se preocupasse apenas com um resultado verdadeiro / falso, dependendo do tipo de string / substring ao qual será aplicado.

O código do Mathematica a seguir quase detecta se a lista é repetida pelo menos uma vez. Se a sequência for repetida pelo menos uma vez, ela retornará verdadeiro, mas também poderá retornar verdadeiro se a sequência for uma combinação linear de sequências repetidas.

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

Esse código procura a contribuição "de comprimento total", que deve ser zero em uma sequência repetida, mas a sequência accbbdtambém é considerada repetida, pois é uma soma das duas sequências repetidas abababe 012012.

A idéia é usar a transformação rápida de Fourier e procurar os espectros de frequência. Olhando para outras frequências, deve-se também detectar esse cenário estranho.

A idéia básica aqui é examinar qualquer possível substring, começando no comprimento 1 e parando na metade do comprimento da string original. Nós olhamos apenas os comprimentos de substring que dividem o comprimento da string original igualmente (ou seja, str.length% substring.length == 0).

Essa implementação examina o primeiro caractere de cada possível iteração de substring antes de passar para o segundo caractere, o que pode economizar tempo se for esperado que as substrings sejam longas. Se nenhuma incompatibilidade for encontrada após examinar toda a substring, retornaremos true.

Retornamos false quando ficamos sem substrings em potencial para verificar.

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

Eu não estou familiarizado com JavaScript, então não sei o quão rápido isso será, mas aqui está uma solução de tempo linear (assumindo uma implementação interna razoável) usando apenas os internos. Vou descrever o algoritmo em pseudocódigo.

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;
}

A ideia é semelhante à resposta do MBo. Para cada um ique divide o comprimento, stré uma repetição de seus primeiros icaracteres se e somente se permanecer o mesmo após a troca de icaracteres.

Me vem à mente que esse componente interno pode estar indisponível ou ineficiente. Nesse caso, sempre é possível implementar o algoritmo KMP manualmente, o que requer aproximadamente a mesma quantidade de código que o algoritmo na resposta do MBo.

Uma das idéias simples é substituir a string pela substring de "" e, se houver algum texto, ele será falso, caso contrário, será verdade.

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