Successione palindromica comune più lunga

Question

Esiste un algoritmo efficiente che conti la lunghezza della più lunga sequenza palindromica comune di due stringhe date?

ad esempio:

stringa 1. afbcdfca

stringa 2. bcadfcgyfka

il LCP è 5 e stringa LCP è afcfa.

Answer 1

Sì.

Basta usare un algoritmo per LCS per più di due sequenze.

Se non mi sbaglio, allora

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

Sta a voi per capire le stringhe # 2 e # 4.

Aggiornamento: No, ecco un controesempio: LCS (aba, aba, bab, bab) = ab, ba. LCS non garantisce che la sottosuccessione sia un palindromo, probabilmente è necessario aggiungere questo vincolo. Ad ogni modo, l'equazione di ricorrenza per LCS è un buon punto di partenza.

Se si implementa LCS in uno stile generatore, in modo che generi tutti LCS di lunghezza n, quindi n-1, n-2 ecc., Allora si dovrebbe essere in grado di calcolare in modo abbastanza efficiente il membro comune più lungo in LCS- gen (string1, reverse-string1), LCS-gen (string2, reverse-string2). Ma non ho ancora controllato, se c'è un LCS-gen altamente efficiente.

Answer 2

E 'lo stesso di questo problema: http://code.google.com/codejam/contest/1781488/dashboard#s=p2

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

Nel codice di seguito vi do un metodo cd (s) (che restituisce un dict char, che ti dice dove il carattere successivo o precedente nella stringa è uguale a quel carattere). Usalo per implementare una soluzione di programmazione dinamica per cui ti ho anche fornito un codice di esempio.

Con la programmazione dinamica sono disponibili solo len (s1) * len (s1)/2 in modo che l'ordine (N^2) sia possibile.

L'idea è di prendere un carattere da s1 o non prenderlo. Se si prende il carattere s1, è necessario prenderlo dal fronte e dal retro (di entrambi s1 e s2). Se non lo prendi, vai avanti 1. (questo significa che lo stato di s2 continua a sincronizzarsi con lo stato di s1 perché ti attiri sempre avidamente dall'esterno di entrambi - quindi ti preoccupi solo di quanti stati s1 possono avere).

Questo codice ti dà la maggior parte del modo lì. cd1 (char dict 1) ti aiuta a trovare il prossimo carattere in s1 uguale al carattere che stai (sia in avanti che indietro).

Nel metodo ricorsivo solve() è necessario decidere su cosa dovrebbero essere start1, end1 .. ecc. Aggiungere 2 al totale ogni volta che si prende un personaggio (a meno che non start1 == END1 - quindi aggiungere 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

Ecco la mia linea di walkthrough infallibile per riga dal momento che questo è abbastanza comune e la maggior parte delle volte le persone a spiegare la dinamica programmare la parte 70% e fermarsi ai dettagli sanguinosi.

1) ottimale Sottostruttura: Sia X[0..n-1] tramite la sequenza di input di lunghezza n e L(0, n-1) essere la lunghezza della più lunga sottosequenza palindromo di X[0..n-1].

Se ultimi e primi caratteri di X sono uguali, allora L(0, n-1) = L(1, n-2) + 2. aspetta perché, e se il secondo e il penultimo carattere non sono lo uguali, non sarebbe l'ultimo e il primo bing lo stesso essere inutile. No, questa "sottosuccessione" non deve essere 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)); 
} 

Considerando quanto sopra attuazione, seguito è un albero ricorsione parziale per una sequenza di lunghezza 6 con tutti i caratteri diversi.

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

Nella suddetta albero di ricorsione parziale, L(1, 4) si sta risolvendo due volte. Se disegniamo l'albero di ricorsione completo, possiamo vedere che ci sono molti sottoproblemi che vengono risolti ancora e ancora. Come altri tipici problemi di programmazione dinamica (DP), è possibile evitare ricalcole degli stessi sottoproblemi costruendo un array temporaneo L[][] in modo ascendente.

// Restituisce la lunghezza della più lunga sottosequenza palindromi in SEQ

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]; 
} 

quindi questo è proprio come la programmazione non dinamica logicamente, è solo qui abbiamo salvare il risultato in un array in modo da non calcoliamo la stessa cosa più e più volte