ultimo - split javascript array

Encontrar cadenas periódicas utilizando funciones de cadena

Question

Estoy buscando una manera de verificar si una cadena es periódica o no usa JavaScript.

La cadena de muestra que debe coincidir puede ser 11223331122333 . Considerando que, 10101 no debe coincidir.

Viniendo de python, usé el RegEx

/(.+?)/1+$/

Pero es bastante lento. ¿Hay algún método de cadena que puede hacer el truco?

Answer 1

Hay una respuesta que merece ser mencionada por su belleza pura. No es mío, solo lo he adaptado de la versión de Python, que está aquí: ¿Cómo puedo saber si una cadena se repite en Python?

function is_periodic(s)
{
   return (s + s.substring(0, s.length >> 1)).indexOf(s, 1) > 0;
}

Desafortunadamente, la velocidad no está a la par con la belleza (y también la belleza ha sufrido un poco en la adaptación de Python, ya que indexOf() tiene un parámetro de inicio, pero no un parámetro de parada). Una comparación con la (s) solución (es) de expresiones regulares y con las funciones de mi otra respuesta está jsperf.com/periodic-strings-1/8 . Incluso con cadenas de longitud aleatoria en [4, 400] basadas en un pequeño alfabeto de 4 caracteres, las funciones de mi otra respuesta funcionan mejor. Sin embargo, esta solución es más rápida que la (s) solución (es) de expresiones regulares.

Esta solución podría denominarse “solución de cambio de fase” . La cuerda se trata como una onda que es idéntica a sí misma cuando se cambia de fase.

La ventaja de esta solución sobre las de mi otra respuesta es que puede adaptarse fácilmente para devolver la subcadena de repetición más corta, como esta:

function repeating_substr(s)
{
    period = (s + s.substring(0, s.length >> 1)).indexOf(s, 1);
    return period > 0 ? s.substr(0, period) : null;
}

Answer 2

La idea del código a continuación es considerar las subcadenas de todas las longitudes en las que se puede dividir la cadena original, y verificar si se repiten en toda la cadena original. Un método simple es verificar todos los divisores de la longitud desde 1 hasta la raíz cuadrada de la longitud. Son divisores si la división produce un entero, que también es un divisor complementario. Por ejemplo, para una cadena de longitud 100, los divisores son 1, 2, 4, 5, 10 y los divisores complementarios son 100 (no es útil como longitud de subcadena porque la subcadena aparecería solo una vez), 50, 25, 20 (y 10 , que ya hemos encontrado).

function substr_repeats(str, sublen, subcount)
{
   for (var c = 0; c < sublen; c++) {
      var chr = str.charAt(c);
      for (var s = 1; s < subcount; s++) {
         if (chr != str.charAt(sublen * s + c)) {
            return false;
         }
      }
   }
   return true;
}

function is_periodic(str)
{
   var len = str.length;
   if (len < 2) {
      return false;
   }
   if (substr_repeats(str, 1, len)) {
      return true;
   }
   var sqrt_len = Math.sqrt(len);
   for (var n = 2; n <= sqrt_len; n++) { // n: candidate divisor
      var m = len / n; // m: candidate complementary divisor
      if (Math.floor(m) == m) {
         if (substr_repeats(str, m, n) || n != m && substr_repeats(str, n, m)) {
            return true;
         }
      }
   }
   return false;
}

Desafortunadamente, no existe un método de cadena para comparar con una subcadena de otra cadena en su lugar (por ejemplo, en lenguaje C que sería strncmp(str1, str2 + offset, length) ).

Digamos que la cuerda tiene una longitud de 120 y consiste en una subcadena de longitud 6 repetida 20 veces. También puede verlo como si consistiera en una longitud sublime (longitud de la subcadena) 12 repetida 10 veces, longitud sublimada 24 repetida 5 veces, longitud sublimada 30 repetida 4 veces o longitud sublimada 60 repetida 2 veces (las longitudes secundarias vienen dadas por los factores primos de 20 (2 * 2 * 5) aplicado en diferentes combinaciones a 6). Ahora, si verifica si su cadena contiene una longitud sublime de 60 repetidas 2 veces, y la verificación falla, también puede estar seguro de que no contendrá ninguna longitud subluente que sea un divisor (es decir, una combinación de factores primos) de 60 , incluido 6. En otras palabras, muchas verificaciones realizadas por el código anterior son redundantes. Por ejemplo, en el caso de la longitud 120, el código anterior verifica (afortunadamente fallando rápidamente la mayor parte del tiempo) las siguientes sub - longitudes: 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60 (en este orden: 1, 60, 2, 40, 3, 30, 4, 24, 5, 20, 6, 15, 8, 12, 10). De estos, solo son necesarios los siguientes: 24, 40, 60. Estos son 2 * 2 * 2 * 3, 2 * 2 * 2 * 5, 2 * 2 * 3 * 5, es decir, las combinaciones de números primos de 120 ( 2 * 2 * 2 * 3 * 5) con uno de cada cebado (no repetido) eliminado, o, si lo prefiere, 120/5, 120/3, 120/2. Entonces, olvidando por un momento que la factorización prima eficiente no es una tarea simple, podemos restringir nuestros controles de subcadenas repetitivas a subcadenas p de longitud de longitud / p, donde p es un factor de longitud primo. La siguiente es la implementación no trivial más simple:

function substr_repeats(str, sublen, subcount) { see above }

function distinct_primes(n)
{
   var primes = n % 2 ? [] : [2];
   while (n % 2 == 0) {
      n /= 2;
   }
   for (var p = 3; p * p <= n; p += 2) {
      if (n % p == 0) {
         primes.push(p);
         n /= p;
         while (n % p == 0) {
            n /= p;
         }
      }
   }
   if (n > 1) {
      primes.push(n);
   }
   return primes;
}

function is_periodic(str)
{
   var len = str.length;
   var primes = distinct_primes(len);
   for (var i = primes.length - 1; i >= 0; i--) {
      var sublen = len / primes[i];
      if (substr_repeats(str, sublen, len / sublen)) {
         return true;
      }
   }
   return false;
}

Al probar este código en mi PC con Linux, tuve una sorpresa: en Firefox era mucho más rápido que la primera versión, pero en Chromium era más lento y se hacía más rápido solo para cadenas con longitudes de miles. Finalmente, descubrí que el problema estaba relacionado con la matriz que distinct_primes() crea y pasa a is_periodic() . La solución fue deshacerse de la matriz mediante la fusión de estas dos funciones. El código está abajo y los resultados de la prueba están en http://jsperf.com/periodic-strings-1/5

function substr_repeats(str, sublen, subcount) { see at top }

function is_periodic(str)
{
   var len = str.length;
   var n = len;
   if (n % 2 == 0) {
      n /= 2;
      if (substr_repeats(str, n, 2)) {
         return true;
      }
      while (n % 2 == 0) {
         n /= 2;
      }
   }
   for (var p = 3; p * p <= n; p += 2) {
      if (n % p == 0) {
         if (substr_repeats(str, len / p, p)) {
            return true;
         }
         n /= p;
         while (n % p == 0) {
            n /= p;
         }
      }
   }
   if (n > 1) {
      if (substr_repeats(str, len / n, n)) {
         return true;
      }
   }
   return false;
}

Recuerde que los tiempos recopilados por jsperf.org son absolutos, y que diferentes experimentadores con diferentes máquinas contribuirán a diferentes combinaciones de canales. Debe editar una nueva versión privada del experimento si desea comparar de manera confiable dos motores de JavaScript.

Answer 3

Si una cadena es periódica:

• El último elemento sería también el último elemento del período.
• La longitud del período dividiría la longitud de la cuerda

Así que podemos hacer un algoritmo súper codicioso que tome el último elemento y verifique las ocurrencias hasta la mitad de la longitud. Cuando encontramos uno, verificamos si la longitud de la subcadena divide la longitud principal y solo después de eso probaremos contra la cadena.

function periodic(str){
    for(var i=0; i<=str.length/2; i++){
        if(str[i] === str[str.length-1] && str.length%(i+1) === 0){
            if (str.substr(0,i+1).repeat(str.length/(i+1)) === str){
        return true;
            }
        }
    }
    return false;
}

Answer 4

Un enfoque directo es dividir la cadena en trozos del mismo tamaño y probar si cada mandril es el mismo que el primer trozo. Aquí hay un algoritmo que lo hace al aumentar el tamaño del fragmento de 1 a longitud / 2, omitiendo los tamaños de trozo que no dividen limpiamente la longitud.

function StringUnderTest (str) {
    this.str = str;
    this.halfLength = str.length / 2;
    this.period = 0;
    this.divideIntoLargerChunksUntilPeriodicityDecided = function () {
        this.period += 1;
        if (this.period > this.halfLength)
            return false;
        if (this.str.length % this.period === 0)
            if (this.currentPeriodOk())
                return true;
        return this.divideIntoLargerChunksUntilPeriodicityDecided();
    };
    this.currentPeriodOk = function () {
        var patternIx;
        var chunkIx;
        for (chunkIx=this.period; chunkIx<this.str.length; chunkIx+=this.period)
            for (patternIx=0; patternIx<this.period; ++patternIx)
                if (this.str.charAt(patternIx) != this.str.charAt(chunkIx+patternIx))
                    return false;
        return true;
    };
}

function isPeriodic (str) {
    var s = new StringUnderTest(str);
    return s.divideIntoLargerChunksUntilPeriodicityDecided();
}

Aunque no he probado la velocidad ...

Answer 5

Una opción es continuar usando una expresión regular, pero hacerla ávida al soltar la ? :

/^(.+)/1+$/

Dependiendo de las cadenas de entrada exactas, puede reducir la cantidad de retroceso requerido y acelerar la coincidencia.