Um algoritmo rápido para computar subsequências comuns mais longas

Algoritmos previamente publicados para encontrar a subsequência comum mais longa de duas sequências de comprimento n tiveram um tempo de execução no melhor caso de O(n 2 ). Um algoritmo para este problema é apresentado, que tem um tempo de execução de O((r + n) log n), onde r é o número total de pares ordenados de posições em que as duas sequências coincidem. Assim, no pior caso, o algoritmo tem um tempo de execução de O(n 2 log n). No entanto, para aquelas aplicações em que a maioria das posições de uma sequência coincide com relativamente poucas posições na outra sequência, pode-se esperar um tempo de execução de O(n log n).