Algorytmy zależne od odległości Gdy rzeczywista odległość jest niewielka w porównaniu z długościami napisów, nie zawsze trzeba obliczać całą tablicę. Ukkonen przedstawił algorytmy dokładne, których koszt zależy od ; jeden z wyników z 1985 roku osiąga czas . W tym kontekście określenie „przybliżone dopasowanie napisów” oznacza dopasowanie dopuszczające błędy, a nie przybliżanie samej wartości odległości.
Metody bitowe Gene Myers zaproponował w 1999 roku algorytm bit-wektorowy dla przybliżonego dopasowania wzorca. Wiele stanów programowania dynamicznego reprezentuje się w bitach słowa maszynowego i aktualizuje równolegle za pomocą operacji bitowychGene Myers, „A fast bit-vector algorithm for approximate string matching based on dynamic programming”, Journal of the ACM, t. 46, nr 3, 1999, s. 395–415, doi:10.1145/316542.316550..