Tengo que crear una función que tome una cadena, y debería devolver true o false en función de si la entrada consiste en una secuencia de caracteres repetida. La longitud de la cadena dada siempre es mayor que 1 y 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')) //falseVerificar 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 cuerda.
El segundo problema es que está usando replace() en cada ciclo, lo que lo hace lento. ¿Hay una mejor solución con respecto al rendimiento?
Hay un pequeño teorema ingenioso sobre cuerdas 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 una cierta cantidad de caracteres del frente de la cadena y moverlos hacia atrás. Por ejemplo, la cadena hello podría rotarse para formar cualquiera de estas cadenas:
hello (the trivial rotation) elloh llohe lohel ohellPara ver por qué esto funciona, primero suponga que una cadena consta de k copias repetidas de una cadena w. Luego, al eliminar la primera copia del patrón repetido (w) de la parte delantera de la cuerda y clavarla en la parte posterior, se obtendrá la misma cuerda. La dirección inversa es un poco más complicada de probar, pero la idea es que si rotas una cuerda y recuperas lo que comenzaste, puedes aplicar esa rotación repetidamente para formar mosaicos en la cuerda con múltiples copias del mismo patrón (ese patrón es el cuerda que necesitabas mover 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 lohel es una rotación de hello de la siguiente 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). Entonces, básicamente, solo necesitamos verificar si nuestra cadena x es una subcadena de xx sin permitir que coincida en el primer carácter o en la mitad. Aquí hay una sola línea para eso:
function check(str) { return (str + str).indexOf(str, 1) !== str.length; } Suponiendo que indexOf se implemente utilizando un algoritmo de coincidencia de cadena rápida, 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 una referencia inversa . Simplemente 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')) //falseEn el anterior RegExp:
^ y $ representan anclas de inicio y final para predecir la posición.(.+) captura cualquier patrón y captura el valor (excepto \n ).\1 es una referencia inversa 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 i-ésimo elemento 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 s y 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 z-array 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 i que dividen n. Si encuentra tal i que i+z[i]=n entonces la cadena s se puede comprimir a la longitud i y puede devolver true .
por ejemplo, para
string s= 'abacabacabac' with length n=12`matriz z es
(0, 0, 1, 0, 8, 0, 1, 0, 4, 0, 1, 0)y podemos encontrar que para
i=4 i+z[i] = 4 + 8 = 12 = n and n % i = 12 % 4 = 0` entonces s podría representarse como una subcadena de longitud 4 repetida tres veces.