¿Cómo verifico si una cadena está hecha completamente de la misma subcadena?

Tengo que crear una función que tome una cadena, y debería regresar trueo falsebasarse en si la entrada consiste en una secuencia de caracteres repetida. La longitud de la cadena dada siempre es mayor 1y la secuencia de caracteres debe tener al menos una repetición.

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

He creado la siguiente función:

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

Verificar esto es parte del verdadero problema. No puedo permitirme una solución no eficiente como esta. En primer lugar, está recorriendo la mitad de la cadena.

El segundo problema es que está usando replace()en cada ciclo lo que lo hace lento. ¿Existe una mejor solución con respecto al rendimiento?

Hay un pequeño teorema ingenioso sobre cadenas como estas.

Una cadena consta del mismo patrón repetido varias veces si y solo si la cadena es una rotación no trivial de sí misma.

Aquí, una rotación significa eliminar algunos caracteres del frente de la cadena y moverlos hacia atrás. Por ejemplo, la cadena hellopodría girarse para formar cualquiera de estas cadenas:

hello (the trivial rotation)
elloh 
llohe 
lohel 
ohell 

Para ver por qué esto funciona, primero, suponga que una cadena consiste en k copias repetidas de una cadena w. Luego, eliminar la primera copia del patrón repetido (w) del frente de la cadena y pegarlo en la parte posterior devolverá la misma cadena. La dirección inversa es un poco más difícil de probar, pero la idea es que si gira una cadena y recupera lo que comenzó, puede aplicar esa rotación repetidamente para colocar la cadena en mosaico con varias copias del mismo patrón (ese patrón es el cadena que necesitaba para moverse hasta el final para hacer la rotación).

Ahora la pregunta es cómo verificar si este es el caso. Para eso, hay otro hermoso teorema que podemos usar:

Si x e y son cadenas de la misma longitud, entonces x es una rotación de y si y solo si x es una subcadena de yy.

Como ejemplo, podemos ver que loheles una rotación de la hellosiguiente manera:

hellohello
   ^^^^^

En nuestro caso, sabemos que cada cadena x siempre será una subcadena de xx (aparecerá dos veces, una en cada copia de x). Básicamente, solo tenemos que verificar si nuestra cadena x es una subcadena de xx sin permitir que coincida en el primer carácter o en el medio. Aquí hay una frase para eso:

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

Suponiendo que indexOfse implemente utilizando un algoritmo de coincidencia de cadenas rápido, esto se ejecutará en el tiempo O (n), donde n es la longitud de la cadena de entrada.

¡Espero que esto ayude!

Puede hacerlo mediante un grupo de captura y referencia inversa . Solo verifique que sea la repetición del primer 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

En el RegExp anterior:

1. ^y $representa los anclajes de inicio y fin para predecir la posición.
2. (.+)captura cualquier patrón y captura el valor (excepto \n).
3. \1es la referencia del primer valor capturado y \1+verificaría la repetición del valor capturado.

Explicación de expresiones regulares aquí

Para el uso de depuración RegExp: https://regex101.com/r/pqlAuP/1/debugger

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

Quizás el enfoque algorítmico más rápido es construir una función Z en tiempo lineal:

La función Z para esta cadena es una matriz de longitud n donde el elemento i-ésimo es igual al mayor número de caracteres a partir de la posición i que coinciden con los primeros caracteres de s.

En otras palabras, z [i] es la longitud del prefijo común más largo entre sy el sufijo de s que comienza en i.

Implementación de C ++ para referencia:

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

Implementación de JavaScript
Optimizaciones agregadas: creación de la mitad de la matriz z y salida anticipada

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

Luego debe verificar los índices ique dividen n. Si encuentra tales ique i+z[i]=nentonces la cadena sse puede comprimir a la longitud iy puede volver true.

Por ejemplo, para

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

z-array es

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

y podemos encontrar eso para

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

entonces spodría representarse como una subcadena de longitud 4 repetida tres veces.

Leí la respuesta de gnasher729 y la implementé. La idea es que si hay repeticiones, debe haber (también) un número primo de repeticiones.

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
}

Un algoritmo ligeramente diferente es este:

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
}

He actualizado la página jsPerf que contiene los algoritmos utilizados en esta página.

Suponga que la cadena S tiene longitud N y está hecha de duplicados de la subcadena s, luego la longitud de s divide N. Por ejemplo, si S tiene longitud 15, entonces la subcadena tiene longitud 1, 3 o 5.

Sea S hecho de (p * q) copias de s. Entonces S también está hecho de p copias de (s, repetidas q veces). Por lo tanto, tenemos dos casos: si N es primo o 1, entonces S solo puede estar hecho de copias de la subcadena de longitud 1. Si N es compuesto, entonces solo necesitamos verificar las subcadenas s de longitud N / p para los primos p dividiendo la longitud de S.

Entonces determine N = la longitud de S, luego encuentre todos sus factores primos en el tiempo O (sqrt (N)). Si solo hay un factor N, verifique si S es la misma cadena repetida N veces; de lo contrario, para cada factor primo p, verifique si S consiste en repeticiones p de los primeros N / p caracteres.

Creo que una función recursiva también podría ser muy rápida. La primera observación es que la longitud máxima del patrón repetido es la mitad del largo de la cadena total. Y podríamos probar todas las longitudes posibles de patrones repetidos: 1, 2, 3, ..., longitud de str / 2

La función recursiva isRepeating (p, str) prueba si este patrón se repite en str.

Si str es más largo que el patrón, la recursión requiere que la primera parte (la misma longitud que p) sea una repetición, así como el resto de str. Entonces str se divide efectivamente en pedazos de longitud p.length.

Si el patrón probado y str son del mismo tamaño, la recursión termina aquí, con éxito.

Si la longitud es diferente (sucede para "aba" y el patrón "ab") o si las piezas son diferentes, entonces se devuelve falso, propagando la recursividad.

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

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

Escribió esto en Python. Sé que no es la plataforma, pero tomó 30 minutos de tiempo. PS => PITÓN

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

Mi enfoque es similar al de gnasher729, ya que utiliza la longitud potencial de la subcadena como el foco principal, pero es menos matemático y requiere un proceso intensivo:

L: longitud de la cuerda original

S: longitudes potenciales de subcadenas válidas

Bucle S de (parte entera de) L / 2 a 1. Si L / S es un entero, verifique su cadena original con los primeros caracteres S de la cadena original repetidos L / S veces.

La razón para realizar un bucle desde L / 2 hacia atrás y no desde 1 en adelante es para obtener la subcadena más grande posible. Si desea el bucle de subcadena más pequeño posible de 1 a L / 2. Ejemplo: "abababab" tiene "ab" y "abab" como posibles subcadenas. ¿Cuál de los dos sería más rápido si solo le importa un resultado verdadero / falso depende del tipo de cadenas / subcadenas a las que se aplicará?

El siguiente código de Mathematica casi detecta si la lista se repite al menos una vez. Si la cadena se repite al menos una vez, devuelve verdadero, pero también puede devolver verdadero si la cadena es una combinación lineal de cadenas repetidas.

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

Este código busca la contribución de "longitud completa", que debe ser cero en una cadena repetitiva, pero la cadena accbbdtambién se considera repetida, ya que es una suma de las dos cadenas repetidas abababy 012012.

La idea es usar la Transformada rápida de Fourier y buscar los espectros de frecuencia. Al observar otras frecuencias, uno también debería ser capaz de detectar este extraño escenario.

La idea básica aquí es examinar cualquier subcadena potencial, comenzando en la longitud 1 y deteniéndose en la mitad de la longitud de la cadena original. Solo observamos las longitudes de las subcadenas que dividen la longitud de la cadena original de manera uniforme (es decir, longitud de cadena% substring.length == 0).

Esta implementación analiza el primer carácter de cada posible iteración de subcadena antes de pasar al segundo carácter, lo que podría ahorrar tiempo si se espera que las subcadenas sean largas. Si no se encuentra ninguna discrepancia después de examinar toda la subcadena, entonces devolvemos verdadero.

Devuelve falso cuando nos quedamos sin subcadenas potenciales 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

No estoy familiarizado con JavaScript, por lo que no sé qué tan rápido será, pero aquí hay una solución de tiempo lineal (suponiendo una implementación integrada razonable) utilizando solo las incorporadas. Describiré el algoritmo en 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;
}

La idea es similar a la respuesta de MBo. Para cada uno ique divide la longitud, stres una repetición de sus primeros icaracteres si y solo si permanece igual después de cambiar de icaracteres.

Me viene a la mente que tal construcción puede no estar disponible o ser ineficiente. En este caso, siempre es posible implementar el algoritmo KMP manualmente, que requiere aproximadamente la misma cantidad de código que el algoritmo en la respuesta de MBo.

Una de las ideas simples es reemplazar la cadena con la subcadena de "" y si existe algún texto, entonces es falso, de lo contrario es cierto.

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