Questo metodo è corretto la sottostringa comune più lunga?

Question

Ho trovato un algoritmo per Supplessione comune più lunga . Di solito è fatto usando dynamic programming, utilizzando un array di dimensioni 2-D di generazione mxn in cui m e n sono lunghezze delle due stringhe in esame.

Costruiremo la seguente matrice per le due stringhe.

M[i][j] = 1 if s1[i]==s2[j] else 0.

Ad esempio, se le stringhe sono: abcxy e pqaabx

La matrice sembra segue:

    a b c x y
 p  0 0 0 0 0
 q  0 0 0 0 0
 a  1 0 0 0 0
 a  1 0 0 0 0
 b  0 1 0 0 0
 x  0 0 0 1 0

.

Ora, cerco una maxima sequenza continua di 1s in ogni diagonale che si trova nella direzione in alto a sinistra a fondo a destra.

Il valore massimo tra queste sarà la risposta.

Posso eseguire l'operazione di cui sopra senza utilizzare esplicitamente l'array. La complessità del tempo è ancora O(M*N). Quindi, non c'è bisogno di memoria.

Qualcuno può indicarmi dove sto sbagliando?

Answer 1

Il tuo metodo è corretto.Per la prova supponiamo che la sottostringa comune più lunga per S1 e S2 proveniva da S1 [I..J] e S2 [p..q]. ciò implica S1 [I + K]= S2 [P + K]

Tutti si trovano tutti sulla diagonale a partire da (I, P).

La soluzione di programmazione dinamica fa la stessa cosa ma invece di calcolare prima la tabella e passare attraverso i percorsi diagonali, calcola la tabella a seconda del suo genitore diagonale più se corrispondono o meno.

modificato

Il tuo commento sulla soluzione Wikipedia utilizzando la memoria aggiuntiva.È lì solo per chiarezza.In linea di principio è necessario solo due righe della matrice nella soluzione Wikipedia e mantenere il numero massimo corrente in una variabile.Questo è corretto da qualsiasi (I, J) TH Entry in the Matrix

m (i, j)= 1 + m (I-1, J-1) (se s1 [i]== s2 [j])

Come puoi vedere gli elementi di corrente corrente dipendono solo dagli elementi della riga superiore.

Answer 2

Il tuo algoritmo è corretto, ma l'approccio DP standard elimina la seconda fase e rende la soluzione più semplice.

Invece di contrassegnare i valori booleani e quindi eseguire la scansione delle diagonali per cercare sequenze più lunghe, è possibile calcolare le lunghezze diagonali mentre si crea la matrice - è necessario solo un passaggio.

In termini di tempo e complessità spaziale, entrambe le soluzioni sono o (NXM).La tua soluzione può salvare una memoria se si utilizza una rappresentazione a matrice di bit, mentre l'altra soluzione è probabilmente leggermente più veloce.