A Fast Algorithm for the Inexact Characteristic String Problem
Moritz G. Maaß · 2003
Abstract We present a new algorithm to solve the INEXACT CHARACTERISTIC STRING PROBLEM using Hamming distance instead of Levenshtein distance as a measure. We embedour new algorithm and the previously known algorithm for Levenshtein distance in a common framework which reveals an additional improvement to the Levenshtein distance al-gorithm. The I NEXACT CHARACTERISTIC STRING PROBLEM can thus be solved in time O(jjT jj + l \\Delta jjS n T jj) for Hamming distance and in time O(jjT jj + k \\Delta l \\Delta jjS n T jj) forLevenshtein distance, where S ` \\Sigma