Detecção de Palíndromos Aproximados em Cadeias
Autores
|
1789 |
163,485
|
|
|
1790 |
163,485
|
Informações:
Publicações do PESC
Nesta tese apresentamos um algoritmo para computar todos os palíndromos aproximados em uma cadeia S de tamanho N. Nossa definição de um palíndromo aproximado é baseada no problema de k-diferenças, que é o caso particular do problema de edição de cadeias que limita o número de erros a no máximo k. Adaptamos um algoritmo para o casamento de cadeias aproximado para resolver o problema de k-diferenças, que nos permitiu achar um palíndromo num tempo de O(k2). Desde que temos O(N) palíndromos na cadeia S, um tempo de O(k2N) foi suficiente para acharmos todos os palíndromos. Também melhoramos o algoritmo resultante através de duas otimizações que conduziram a melhores tempos na prática. Uma grande quantidade de resultados experimentais foram apresentados.
In this tesis we give an algorithm for finding all approximate palindromes in a string S of length N. Our definition of an approximate palindrome is based on the problem of k-differences, which is the particular case of the string editing problem that limits the number of erros at no more than k. We have adapted an algorithm for approximate string matching to solve the k-differences problem, which has allowed us to find a palindrome in O(k2) time. Because we have O(N) palindromes in string S, a time of O(k2N) suffices for all palindromes to be found. We have also improved the resulting algorithm by two optimizations that lead to better times in practice. Extensive experimental results are presented.