É este o método mais comum de subseqüência de caracteres correto?

Question

Eu encontrei um algoritmo para Maior Subcadeia Comum.Ele geralmente é feito usando dynamic programming, usando uma matriz 2-D de tamanho mxn onde m e n são os comprimentos das duas seqüências em consideração.

Eu vou construir a matriz a seguir para as duas cadeias de caracteres.

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

Por exemplo, se as cadeias de caracteres são: abcxy e pqaabx

A matriz de procura da seguinte forma:

    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

Agora, eu procuro para um máximo de seqüência contínua de 1s em cada diagonal que está em cima-esquerda-baixo-direita.

O valor máximo entre estes será a resposta.

Posso executar a operação acima sem utilizar a matriz explicitamente.O tempo-a complexidade é ainda O(M*N).Assim, não há necessidade de memória.

Alguém pode me aponte onde eu estou errado?

Answer 1

Seu método é correto.Para a prova suponha que a maior subcadeia comum para S1 e S2 foi a partir de S1[i..j] e S2[p..q].isto implica S1[i+k] = S2[p+k]

Todas essas estão na diagonal, começando a partir de (i,p).

A programação dinâmica solução faz a mesma coisa, mas em vez de calcular a tabela de primeira e passando por diagonal caminhos calcula a tabela dependendo da diagonal principal acrescido ou não de correspondência.

EDITADO

Em seu comentário sobre a solução da wikipedia utilizar memória adicional.Ele está lá apenas para maior clareza.Em princípio, você só precisa de duas linhas da matriz a solução da wikipedia e manter a atual contagem máxima, em uma variável.Isso está correto, desde que para (i,j)th entrada na matriz

M(i,j) = 1 + M(i-1, j-1) (se s1[i] == s2[j])

como você pode ver a linha actual elementos dependem apenas os elementos de a imediatamente superior da linha.

Answer 2

O seu algoritmo está correto, mas o padrão DP abordagem elimina a sua segunda fase, e torna a solução mais simples.

Em vez de marcar os valores booleanos e, em seguida, a digitalização diagonais para procurar mais longas sequências, você pode calcular a diagonal de comprimentos de como você construir a matriz - Apenas um passo é necessário.

Em termos de tempo e espaço complexidade, ambas as soluções são O(NxM).A solução pode economizar memória se você usar um pouco de matriz de representação, enquanto a outra solução é, provavelmente, um pouco mais rápido.