Checking Time Linearity of Regular Expression Matching Based on Backtracking.
Satoshi SugiyamaYasuhiko MinamidePublished in: Inf. Media Technol. (2014)
Keyphrases
- regular expressions
- pattern matching
- approximate matching
- matching algorithm
- string matching
- semistructured data
- regular path queries
- finite automata
- graph matching
- deterministic finite automata
- query language
- cost model
- approximate string matching
- search algorithm
- edit distance
- data sets
- query evaluation
- suffix array
- semi automatic