2008 | OriginalPaper | Buchkapitel
Pattern Matching in DCA Coded Text
verfasst von : Jan Lahoda, Bořivoj Melichar, Jan Žd’árek
Erschienen in: Implementation and Applications of Automata
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
A new algorithm searching all occurrences of a regular expression pattern in a text is presented. It uses only the text that has been compressed by the text compression using antidictionaries without its decompression. The proposed algorithm runs in
${\mathcal O}(2^m\cdot||{\rm AD}||^2+n_c+r)$
worst case time, where
m
is the length of the pattern, AD is the antidictionary,
n
C
is the length of the coded text and
r
is the number of found matches.