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

string algorithm

Question

Tengo que crear una función que tome una cadena, y debería devolver true o false 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'')) //false

La comprobación de esto es parte del problema real. No puedo permitirme una solución no eficiente como esta. En primer lugar, se recorre la mitad de la cadena.

El segundo problema es que está utilizando replace() en cada bucle, lo que lo hace lento. ¿Hay una mejor solución con respecto al rendimiento?

Answer 1

Creo que una función recursiva podría ser muy rápida también. 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 simplemente probar todas las posibles longitudes de patrones repetidos: 1, 2, 3, ..., str.length / 2

La función recursiva isRepeating (p, str) comprueba 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. Así que str se divide efectivamente en trozos de longitud p.longitud.

Si el patrón y la cadena probados son de igual tamaño, la recursión termina aquí, con éxito.

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

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

Answer 2

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 de repetición, pero la cadena accbbd también se considera repetida, ya que es una suma de las dos cadenas repetidas ababab y 012012 .

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

Answer 3

Escribí esto en Python. Sé que no es la plataforma, pero tomó 30 minutos de tiempo. 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")

Answer 4

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

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

Aquí, una rotación significa eliminar un cierto número de caracteres de la parte delantera de la cadena y moverlos hacia atrás. Por ejemplo, la cadena hello se puede rotar para formar cualquiera de estas cadenas:

hello (the trivial rotation)
elloh
llohe
lohel
ohell 

Para ver por qué funciona esto, primero, suponga que una cadena consiste en k copias repetidas de una cadena w. Luego, al eliminar la primera copia del patrón repetido (w) de la parte delantera de la cadena y pegarlo en la parte posterior, se 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 formar una cadena con múltiples copias del mismo patrón (ese patrón es el cadena que necesitabas para moverte 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 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). Básicamente, solo necesitamos verificar si nuestra cadena x es una subcadena de xx sin permitir que coincida en el primer carácter o la mitad del camino. Aquí hay una frase para eso:

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

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

¡Espero que esto ayude!

Answer 5

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

Esta implementación analiza el primer carácter de cada posible iteración de subcadenas 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 una discrepancia después de examinar toda la subcadena, devolvemos true.

Devolvemos false 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

Answer 6

Leí la respuesta de gnasher729 y la implementé. La idea es que si hay repeticiones, entonces 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.

Answer 7

Mi enfoque es similar a gnasher729, ya que utiliza la longitud potencial de la subcadena como enfoque principal, pero es menos matemático y requiere mucho más proceso:

L: Longitud de la cuerda original

S: longitudes potenciales de subcadenas válidas

El bucle S de (parte entera de) L / 2 a 1. Si L / S es un número entero, verifique su cadena original contra los primeros caracteres S de la cadena original repetida L / S veces.

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

Answer 8

No estoy familiarizado con JavaScript, por lo que no sé qué tan rápido va a ser esto, pero aquí hay una solución de tiempo lineal (suponiendo una implementación integrada razonable) utilizando solo los incorporados. Voy a 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 i que divide la longitud, str es una repetición de sus primeros caracteres i si y solo si permanece igual después de cambiar para i caracteres.

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

Answer 9

Puedes hacerlo por un grupo de captura y backreference . Solo verifica 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 $ son los anclajes de inicio y final para predecir la posición.
2. (.+) captura cualquier patrón y captura el valor (excepto /n ).
3. /1 es una referencia inversa del primer valor capturado y /1+ verificará la repetición del valor capturado.

Explicacion de regex aqui

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

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

Answer 10

Quizás el enfoque algorítmico más rápido es construir una Z-function en el tiempo lineal:

La función Z para esta cadena es una matriz de longitud n donde el elemento i-th es igual al mayor número de caracteres que comienzan desde 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 - construyendo la mitad de z-array y salida temprana

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

Entonces necesitas 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`

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`

por lo que s podría representarse como una subcadena de longitud 4 repetida tres veces.

Answer 11

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

Sea S 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 se puede hacer de copias de la subcadena de longitud 1. Si N es compuesto, solo necesitamos verificar las subcadenas de longitud N / p para los primos que se dividen 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 se compone de repeticiones p de los primeros caracteres N / p.

Answer 12

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 verdadero.

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