|
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 |
|
