Pattern Matching on Grammar-Compressed Strings in Linear Time.
Moses GanardiPawel GawrychowskiPublished in: SODA (2022)
Keyphrases
- pattern matching
- suffix array
- string matching
- suffix tree
- approximate string matching
- regular expressions
- context free grammars
- natural language
- pattern matching algorithm
- matching process
- bit parallel
- compressed pattern matching
- data structure
- graph matching
- finite state automata
- hamming distance
- grammatical inference
- tree matching
- approximate pattern matching