Células preenchidas
Pares iguais
Mais longa até agora

  • A preencher
  • Lida
  • Resposta

Mais sobre a subsequência comum mais longa

Subsequência comum mais longa (LCS)

Que letras têm duas palavras em comum, pela mesma ordem? A subsequência comum mais longa responde a isso, e as ferramentas diff, os corretores ortográficos e as comparações de ADN baseiam-se nela. Escreva duas palavras e veja uma tabela das suas letras a encher-se; depois reconstrua a resposta a partir do canto. Prima Reproduzir para ver a tabela a encher-se, ou Avançar e Recuar para ir um passo de cada vez. Arraste a barra de passos para saltar para qualquer ponto. Escreva duas palavras: a primeira fica ao longo do lado da tabela e a segunda ao longo do topo. Cada célula guarda o comprimento da subsequência comum mais longa das letras até à sua linha e à sua coluna. No fim, as letras são lidas de volta a partir da célula do canto inferior direito. Novo exemplo escolhe outro par de palavras. Com o tabuleiro selecionado, as setas avançam e recuam um passo, a barra de espaço reproduz e pausa, e Home e End saltam para o início e o fim.

Como funciona

  1. Escreva duas palavras: a primeira fica ao longo do lado da tabela e a segunda ao longo do topo.
  2. Prima Reproduzir, ou use Avançar e Recuar para ir um passo de cada vez. Arraste a barra de passos para saltar para qualquer ponto.
  3. Veja cada célula comparar as suas duas letras e depois siga o caminho laranja a partir do canto para ler a resposta.

Como funciona a tabela

Uma célula guarda o comprimento da subsequência comum mais longa entre as letras da primeira palavra até à sua linha e as letras da segunda palavra até à sua coluna. A linha e a coluna marcadas com – representam uma palavra vazia, por isso valem 0. Se as duas letras de uma célula forem iguais, a célula vale mais um do que a célula acima à esquerda. Se forem diferentes, uma das duas letras não faz parte da resposta, por isso a célula fica com o maior valor entre a célula de cima e a da esquerda.

Ler as letras de volta

A célula do canto inferior direito é o comprimento da resposta. Para encontrar as letras, comece aí: onde as duas letras coincidem, essa letra faz parte da subsequência e avança para cima e para a esquerda; caso contrário, vai para a maior entre a célula de cima e a da esquerda. As letras recolhidas pelo caminho, lidas ao contrário, formam uma subsequência comum mais longa. Pode haver outras com o mesmo comprimento; a leitura de volta encontra uma delas.

Perguntas frequentes

Qual é a diferença entre uma subsequência e uma subcadeia?

Uma subcadeia é uma série de letras seguidas, como ACE em RACER. Uma subsequência mantém a ordem mas pode saltar letras, por isso ACE também é uma subsequência de ABCDE. A subcadeia comum mais longa é um problema diferente, com uma tabela semelhante.

Quão rápido é o algoritmo LCS?

Para palavras de comprimentos m e n, a tabela tem m·n células, cada uma preenchida num passo, por isso o trabalho é O(m·n). Para dois textos de 10 000 linhas são 100 milhões de células, e é por isso que as ferramentas diff usam métodos mais engenhosos baseados na mesma ideia.

A subsequência comum mais longa é única?

Não. ABCBDAB e BDCABA têm três subsequências comuns diferentes de comprimento 4: BCBA, BCAB e BDAB. A tabela dá o comprimento; a leitura de volta escolhe uma delas.

A LCS diz quão parecidas são duas palavras?

Em parte. Duas palavras de comprimentos m e n com uma subsequência comum mais longa de comprimento k podem ser transformadas uma na outra apagando m − k letras e inserindo n − k. A distância de edição, que também permite substituir uma letra, é muitas vezes uma medida melhor.

É enviado algum dado para algum lado?

Não. Tudo é calculado no seu navegador, e as suas últimas definições ficam guardadas no armazenamento local deste navegador.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Ir para o editor