Questo metodo è corretto la sottostringa comune più lunga?
-
23-12-2019 - |
Domanda
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 1
s 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?
Soluzione
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.
Altri suggerimenti
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.