Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
A New Algorithm for the Characteristic String Problem under Loose Similarity Criteria
verfasst von : Yoshifumi Sakai
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Given two strings
S
and
T
, together with an integer representing the similarity bound, the characteristic string problem consists in finding the shortest substrings of
T
such that
S
has no substrings similar to them, in the sense that one string is similar to another if the amount of ‘dissimilarities’ between them is less than or equal to the similarity bound. Under the similarity criterion that uses Levenshtain distance to measure the amount of dissimilarities between two strings, this problem is known to be solvable in cubic time and linear space. The present article proposes a new algorithm for this problem that performs in almost quadratic time and almost linear space, under a certain class of similarity criteria, including the similarity criterion based on Levenshtain distance.