Subsección palindrómica común más larga

Question

¿Hay algún algoritmo eficiente que cuente la longitud de la subsección palindrómica común más larga de dos cadenas dadas?

por ejemplo:

cadena 1. afbcdfca

cadena 2. bcadfcgyfka

la LCPS es 5 y la cadena LCPS es afcfa.

Answer 1

Sí.

Simplemente use un algoritmo para LCS para más de dos secuencias.

Si no estoy equivocado, entonces

LCS(afbcdfca, acfdcbfa, bcadfcgyfka, akfygcfdacb) = afcfa 

Depende de usted para averiguar cuerdas # 2 y # 4.

Actualización: No, aquí hay un contraejemplo: LCS (aba, aba, bab, bab) = ab, ba. El LCS no garantiza que la subsecuencia sea un palíndromo, es probable que necesite agregar esta restricción. De todos modos, la ecuación de recurrencia para LCS es un buen punto de partida.

Si implementa LCS en un estilo de generador, de modo que genere todos los LCS de longitud n, entonces n-1, n-2, etc., entonces debería poder calcular bastante eficientemente el miembro común más largo en LCS- gen (string1, reverse-string1), LCS-gen (string2, reverse-string2). Pero aún no lo he comprobado, si hay un LCS-gen altamente eficiente.

Answer 2

Es lo mismo que este problema: http://code.google.com/codejam/contest/1781488/dashboard#s=p2

http://code.google.com/codejam/contest/1781488/dashboard#s=a&a=2

En el código de abajo te doy un método de CD (s) (que devuelve un diccionario carbón que le dice que el siguiente o anterior Char en la cadena es que es igual a ese char). Úselo para implementar una solución de programación dinámica para la cual también le he dado un código de muestra.

Con la programación dinámica solo existen los estados len (s1) * len (s1)/2, por lo que es posible el orden (N^2).

La idea es tomar un char de s1 o no tomarlo. Si quita el carácter s1, debe tomarlo desde la parte frontal y posterior (tanto de s1 como de s2). Si no lo tomas, te mueves 1. (esto significa que el estado de s2 se mantiene sincronizado con el estado de s1 porque siempre tomas codiciosamente desde el exterior de ambos, por lo que solo te preocupes por cuántos estados puede tener s1)

Este código te lleva la mayor parte del camino hasta allí. cd1 (char dict 1) te ayuda a encontrar el siguiente caracter en s1 igual al char en el que estás (tanto hacia adelante como hacia atrás).

En el método recursivo solve() debe decidir qué start1, end1 ... etc. debería ser. Añadir 2 al total cada vez que toma un carácter (a menos start1 == END1 - a continuación, agregar 1)

s1 = "afbcdfca" 
s2 = "bcadfcgyfka" 

def cd(s): 
    """returns dictionary d where d[i] = j where j is the next occurrence of character i""" 
    char_dict = {} 
    last_pos = {} 
    for i, char in enumerate(s): 
     if char in char_dict: 
      _, forward, backward = char_dict[char] 
      pos = last_pos[char] 
      forward[pos] = i 
      backward[i] = pos 
      last_pos[char] = i 
     else: 
      first, forward, backward = i, {}, {} 
      char_dict[char] = (first, forward, backward) 
      last_pos[char] = i 
    return char_dict 

print cd(s1) 
"""{'a': ({0: 7}, {7: 0}), 'c': ({3: 6}, {6: 3}), 'b': ({}, {}), 'd': ({}, {}), 'f': ({1: 5}, {5: 1})}""" 

cd1, cd2 = cd(s1), cd(s2) 

cache = {} 
def solve(start1, end1, start2, end2): 
    state = (start1, end1) 
    answer = cache.get(state, None) 
    if answer: 
     return answer 

    if start1 < end1: 
     return 0 
    c1s, c1e = s1[start1], s1[end1] 
    c2s, c2e = s2[start2], s2[end2] 

    #if any of c1s, c1e, c2s, c2e are equal and you don't take, you must 
    #skip over those characters too: 
    dont_take_end1 = solve(start1, end1 - 1, start2, end2) 

    do_take_end1 = 2 
    if do_take_end1: 
     end1_char = s1[end1] 
     #start1 = next character along from start1 that equals end1_char 
     #end1 = next char before end1 that equals end1_char 
     #end2 = next char before end2 that.. 
     #start2 = next char after .. that .. 
     do_take_end1 += solve(start1, end1, start2, end2) 


    answer = cache[state] = max(dont_take_end1, do_take_end1) 
    return answer 

print solve(0, len(s1), 0, len(s2)) 

Answer 3

Aquí está mi línea de recorrido a toda prueba por línea ya que esto es muy común y la mayoría de las veces la gente a explicar la dinámica programación parte 70% y detenerse en los detalles sangrientos.

1) Optimal Subestructura: Vamos X[0..n-1] ser la secuencia de entrada de longitud n y L(0, n-1) ser la longitud de la subsecuencia palindrómica más largo de X[0..n-1].

Si últimos y primeros caracteres de X son los mismos, entonces L(0, n-1) = L(1, n-2) + 2. Espera por qué, ¿qué pasa si el segundo y el segundo al último caracteres no son lo mismo, no sería el último y el primer bing el mismo ser inútil. no, esta "subsecuencia" no tiene que ser continua.

/* Driver program to test above functions */ 
int main() 
{ 
    char seq[] = "panamamanap"; 
    int n = strlen(seq); 
    printf ("The lnegth of the LPS is %d", lps(seq, 0, n-1)); 
    getchar(); 
    return 0; 
} 

int lps(char *seq, int i, int j) 
{ 
    // Base Case 1: If there is only 1 character 
    if (i == j)  
     return 1;  

    // Base Case 2: If there are only 2 characters and both are same 
    if (seq[i] == seq[j] && i + 1 == j)  
     return 2;  

    // If the first and last characters match 
    if (seq[i] == seq[j])  
     return lps (seq, i+1, j-1) + 2;  

    // If the first and last characters do not match 
    else return max(lps(seq, i, j-1), lps(seq, i+1, j)); 
} 

Teniendo en cuenta la implementación anterior, siguiente es un árbol de recursión parcial para una secuencia de longitud 6 con todos los caracteres diferentes.

   L(0, 5) 
      /  \ 
      /  \ 
     L(1,5)   L(0,4) 
    / \   / \ 
    / \  / \ 
    L(2,5) L(1,4) L(1,4) L(0,3) 

En el árbol de recursión parcial anteriormente, L(1, 4) se está resolviendo dos veces. Si dibujamos el árbol de recursión completo, entonces podemos ver que hay muchos subproblemas que se resuelven una y otra vez. Al igual que otros problemas típicos de Programación Dinámica (DP), se pueden evitar los recuentos de los mismos subproblemas construyendo una matriz temporal L[][] de abajo hacia arriba.

// Devuelve la longitud de la subsecuencia palindrómica más larga en la SEC

int lps(char *str) 
{ 
    int n = strlen(str); 
    int i, j, cl; 
    int L[n][n]; // Create a table to store results of subproblems 


    // Strings of length 1 are palindrome of length 1 
    for (i = 0; i < n; i++) 
     L[i][i] = 1; 

    for (cl=2; cl<=n; cl++)        //again this is the length of chain we are considering 
    { 
     for (i=0; i<n-cl+1; i++)       //start at i 
     { 
      j = i+cl-1;         //end at j 
      if (str[i] == str[j] && cl == 2)    //if only 2 characters and they are the same then set L[i][j] = 2 
       L[i][j] = 2; 
      else if (str[i] == str[j])     //if greater than length 2 and first and last characters match, add 2 to the calculated value of the center stripped of both ends 
       L[i][j] = L[i+1][j-1] + 2; 
      else 
       L[i][j] = max(L[i][j-1], L[i+1][j]);  //if not match, then take max of 2 possibilities 
     } 
    } 

    return L[0][n-1]; 
} 

por lo que este es igual que la programación dinámica no lógicamente, es sólo que aquí nos guardar el resultado en una matriz por lo que no calculamos lo mismo una y otra vez