En Word factorización

12

Dadas dos cadenas S1,S2 , escribimos S1S2 para su concatenación. Dada una cadena S y número entero k1 , escribimos (S)k=SSS para la concatenación de k copias de S . Ahora dada una cadena, podemos usar esta notación para 'comprimirla', es decir, AABAAB puede escribirse como ((A)2B)2 . Llamemos al peso de unacompresiónel número de caracteres que aparecen en él, por lo que el peso de((A)2B2) es dos, y el peso de(AB)2A (unacompresióndeABABA ) es tres (lasA separadasse cuentan por separado).

Ahora considere el problema de calcular la compresión 'más ligera' de una cadena S dada con |S|=n . Después de pensarlo, hay un enfoque de programación dinámica obvio que se ejecuta en O(n3logn) u O(n3) dependiendo del enfoque exacto.

Sin embargo, me han dicho que este problema se puede resolver en tiempo O(n2logn) , 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 O(n3logn) , 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 :-)

Timon Knigge
fuente
SS=Xa=Yb Z gcd ( | X | , | Y | ) X Y S = X a S Y S = Y b Y X | X |S=Z|S|/gcd(|X|,|Y|)Zgcd(|X|,|Y|)XYS=XaSYS=Yb, solo necesita probar los prefijos de con una longitud que divide. YX|X|
j_random_hacker
El problema es que incluso después de reducir todas las posibles , aún necesita agregar la respuesta por un DP cúbico sobre subsegmentos (es decir, ), así que aún queda trabajo por hacer después de eso ... D P [ l , r ] = min k D P [ l , k ] + D P [ k + 1 , r ]XaDP[l,r]=minkDP[l,k]+DP[k+1,r]
Timon Knigge
Veo a que te refieres. Creo que necesita algún tipo de relación de dominio que elimine la necesidad de probar algunos valores de , pero no he podido pensar en uno. En particular, consideré lo siguiente: supongamos que tiene una factorización óptima con ; ¿Es posible que exista una solución óptima en la que se factorice como con ? Lamentablemente, la respuesta es sí: para , tiene una factorización óptima , pero la factorización óptima única para es .S [ 1 .. i ] S [ 1 .. i ] = X Y k k > 1 S X Y j Z j < k S = A B A B C A B C S [ 1..4 ] ( A B ) 2 S A B ( A B C ) 2kS[1..i]S[1..i]=XYkk>1SXYjZj<kS=ABABCABCS[1..4](AB)2SAB(ABC)2
j_random_hacker

Respuestas:

1

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.(pi,ri)=1,2,pi11r2

S[irpi1+1,ipi1]=S[i(r1)pi1+1,i].
pi1ri1rpiLi=0(pi,ri)

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 .pi2(ri11)pi1

S[iri2pi2+1,ipi2]=S[i(ri21)pi2+1,i]
ri22ri2pi2pi(ri11)pi1piLi=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))pipi+1(ri1)pipi/2

Supongamos que ahora se nos dan todos los valores . El costo mínimo viene dado por la recurrencia entendiendo que para configuramos . La tabla se puede llenar en tiempo.(pi,ri)

dp(i,j)=min{dp(i,j1)+1,min(dp(i,jrjpj)+dp(jrjpj+1,jpj))}
i>jdp(i,j)=+O(n2+njLj)

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)SiLiT(S)pijnca(v(i),v(ipij))v(ipij)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)(pij,rij)O(n+iLi)

Avísame si esto tiene sentido.

Mert Sağlam
fuente
-1

Existe su cadena inicial S de longitud n. Aquí está el pseudocódigo del método.

next_end_bracket = n
for i in [0:n]: # main loop

    break if i >= length(S) # due to compression
    w = (next_end_bracket - i)# width to analyse

    for j in [w/2:0:-1]: # period loop, look for largest period first
        for r in [1:n]: # number of repetition loop
            if i+j*(r+1) > w:
                break r loop

            for k in [0:j-i]:
                # compare term to term and break at first difference
                if S[i+k] != S[i+r*j+k]:
                    break r loop

        if r > 1:
            # compress
            replace S[i:i+j*(r+1)] with ( S[i:i+j] )^r
            # don't forget to record end bracket...
            # and reduce w for the i-run, carrying on the j-loop for eventual smaller periods. 
            w = j-i

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.

  • i-loop es O (n)
  • j-loop es O (n)
  • r + k-loops es O (log (n)) ya que se detiene en la primera diferencia

Esto es globalmente O (n²log (n)).

Optidad
fuente
No me queda claro que los bucles r y k son O (log n), incluso por separado. ¿Qué asegura que se encuentre una diferencia después de, como máximo, las iteraciones O (log n)?
j_random_hacker
¿Entiendo correctamente que estás comprimiendo con avidez? Como eso es incorrecto, considere, por ejemplo, ABABCCCABCCC, que debe factorizar como AB (ABC ^ 3) ^ 2.
Timon Knigge
Sí, tienes toda la razón sobre eso, tengo que pensar en esto.
Optidad