Dadas dos cadenas , escribimos para su concatenación. Dada una cadena y número entero , escribimos para la concatenación de copias de . Ahora dada una cadena, podemos usar esta notación para 'comprimirla', es decir, puede escribirse como . Llamemos al peso de unacompresiónel número de caracteres que aparecen en él, por lo que el peso de es dos, y el peso de (unacompresiónde ) es tres (las separadasse cuentan por separado).
Ahora considere el problema de calcular la compresión 'más ligera' de una cadena dada con . Después de pensarlo, hay un enfoque de programación dinámica obvio que se ejecuta en u dependiendo del enfoque exacto.
Sin embargo, me han dicho que este problema se puede resolver en tiempo , aunque no puedo encontrar ninguna fuente sobre cómo hacerlo. Específicamente, este problema se dio en un concurso de programación reciente (problema K aquí , últimas dos páginas). Durante el análisis se presentó un algoritmo , y al final se mencionó el enlace pseudo cuadrático ( aquí en la marca de cuatro minutos). Lamentablemente, el presentador solo se refirió a 'un complicado lema combinatorio de palabras', así que ahora he venido aquí para pedir la solución :-)
fuente
Respuestas:
Si no te estoy malentendiendo, creo que la factorización de costo mínimo se puede calcular en tiempo siguiente manera.O(n2)
Para cada índice i, calcularemos un grupo de valores para siguiente manera. Supongamos que es el número entero más pequeño de modo que haya un número entero satisfagaPara este particular , deje que sea el más grande con esta propiedad. Si no existe tal , establezca para que sepamos que hay valores cero para este índice.(pℓi,rℓi) ℓ=1,2,… p1i≥1 r≥2 S[i−rp1i+1,i−p1i]=S[i−(r−1)p1i+1,i]. p1i r1i r pi Li=0 (pℓi,rℓi)
Deje que sea el entero más pequeño estrictamente más grande que satisfaga, asimismo, para algunos . Como antes, tome como el máximo que tiene fijo . En general, es el número más pequeño estrictamente más grande que . Si no existe tal , entonces .p2i (r1i−1)p1i S[i−r2ip2i+1,i−p2i]=S[i−(r2i−1)p2i+1,i] r2i≥2 r2i p2i pℓi (rℓ−1i−1)pℓ−1i pℓi Li=ℓ−1
Tenga en cuenta que para cada índice i, tenemos debido a que los valores de aumentan geométricamente con . (si existe , no solo es estrictamente mayor que sino que es mayor que al menos Esto establece el aumento geométrico. )Li=O(log(i+1)) pℓi ℓ pℓ+1i (rℓi−1)pℓi pℓi/2
Ya hemos observado anteriormente que al delimitar la suma término por término. Pero en realidad, si miramos la suma total, podemos probar algo más preciso.∑jLj=O(∑jlog(j+1))=Θ(nlogn)
Considere el árbol de sufijos del reverso de (es decir, el árbol de prefijos de S). cada contribución a la suma a un borde de para que cada borde se cargue como máximo una vez. Cargue cada hasta el borde que emana de y vaya hacia . Aquí es la hoja del árbol de prefijos correspondiente a y nca denota el ancestro común más cercano.T(S←) S ∑iLi T(S←) pji nca(v(i),v(i−pji)) v(i−pji) v(i) S[1..i]
Esto muestra que . Los valores se pueden calcular en el tiempo mediante un recorrido del árbol de sufijos, pero dejaré los detalles para una edición posterior si alguien está interesado.O(∑iLi)=O(n) (pji,rji) O(n+∑iLi)
Avísame si esto tiene sentido.
fuente
Existe su cadena inicial S de longitud n. Aquí está el pseudocódigo del método.
Intencionalmente di pequeños detalles sobre "paréntesis finales", ya que necesita muchos pasos para apilar y desapilar, lo que dejaría claro el método central. La idea es probar una eventual contracción adicional dentro de la primera. por ejemplo ABCBCABCBC => (ABCBC) ² => (A (BC) ²) ².
Entonces, el punto principal es buscar períodos grandes primero. Tenga en cuenta que S [i] es el i-ésimo término de S omitiendo cualquier "(", ")" o potencia.
Esto es globalmente O (n²log (n)).
fuente