A simple grammar-based index for finding approximately longest common substrings

Area of Science:

• Computer Science
• Algorithms
• Data Structures

Background:

• Efficiently finding common substrings between large texts and patterns is a fundamental problem in computer science.
• Existing methods often face trade-offs between space complexity, query time, and accuracy.

Purpose of the Study:

• To develop a space-efficient index for identifying substrings of a pattern that are also present in a given text.
• To achieve a query time that is nearly linear in the pattern length while guaranteeing a significant fraction of the longest common substring.

Main Methods:

• Construction of an O(g)-space index based on an alpha-balanced straight-line program for the text.
• Utilizing the index to search for pattern substrings within a specified time complexity.

Main Results:

• The proposed index allows finding a common substring of P and T with a length of at least (1-epsilon) fraction of the longest common substring.
• This is achieved with high probability (w.h.p.) in O(m log^delta g) expected query time, using O(g) space.

Conclusions:

• The study presents a novel approach to approximate longest common substring queries, offering a favorable balance between space and time efficiency.
• The developed index provides a practical solution for applications requiring fast and accurate substring matching.