Graphs Cannot Be Indexed in Polynomial Time for Sub-quadratic Time String Matching, Unless SETH Fails.
Massimo EquiVeli MäkinenAlexandru I. TomescuPublished in: SOFSEM (2021)
Keyphrases
- string matching
- pattern matching
- computational complexity
- edit distance
- approximate string matching
- graph matching
- polynomial time complexity
- approximate matching
- regular expressions
- clone detection
- pairwise
- bounded treewidth
- suffix array
- objective function
- exact and approximate
- suffix tree
- aho corasick
- pattern matching algorithm
- similarity measure
- dynamic programming
- data model
- data structure