View publication

Title A Simple Grammar-based Index for Finding Approximately Longest Common Substrings
Authors Travis Gagie, Sana Kashgouli, Gonzalo Navarro
Publication date 2023
Abstract We show how, given positive constants e and d, and an a-balanced straight-line program with g rules for a text T[1..n], we can build an O(g)-space index that, given a pattern P[1..m], in O(m log^d g) time finds with high probability a substring of P that occurs in T and whose length is at least a (1-e) fraction of the longest common substring of P and T.
Pages 246-252
Conference name International Symposium on String Processing and Information Retrieval
Publisher Springer-Verlag (Berlin/Heidelberg, Germany)
Reference URL View reference page