Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails.
Massimo EquiVeli MäkinenAlexandru I. TomescuPublished in: Theor. Comput. Sci. (2023)
Keyphrases
- string matching
- pattern matching
- computational complexity
- edit distance
- approximate string matching
- graph matching
- polynomial time complexity
- approximate matching
- suffix tree
- bounded treewidth
- pairwise
- regular expressions
- aho corasick
- pattern matching algorithm
- clone detection
- machine learning
- exact and approximate
- data management
- suffix array
- query language
- similarity measure
- information retrieval
- approximate pattern matching