Eu estou usando o algoritmo de Levenshtein para encontrar a semelhança entre duas seqüências de caracteres. Esta é uma parte muito importante do programa que estou fazendo, por isso precisa ser eficaz. O problema é que o algoritmo não encontra os seguintes exemplos como semelhantes:

CONAIR
AIRCON

O algoritmo vai dar uma distância de 6. Então, para esta palavra de 6 letras (você olha para a palavra com a maior quantidade de letras), a diferença é de 100% => a semelhança é de 0%.

Eu preciso encontrar uma maneira de encontrar as semelhanças entre duas seqüências, mas também levando em consideração casos como o que apresentei antes.

Existe um algoritmo melhor que eu possa usar? Ou o que vocês me recomendam?

EDIT: Eu também olhei para o algoritmo "Damerau-Levenshtein", que adiciona transposições. O problema é que essas transposições são apenas para caracteres adjacentes (e não para um número de caracteres).