Advances in String Matching and Indexing

The field of string matching and indexing is witnessing significant developments, driven by the need for efficient and scalable solutions to handle large datasets. Researchers are exploring new approaches to tackle complex problems, such as circular dictionary matching, maximal common subsequence enumeration, and string indexing with utilities. A key trend is the focus on designing algorithms and data structures that can handle arbitrary dictionaries, multiple strings, and numerical scores, while minimizing space and time complexity. Notably, innovative solutions are being proposed to circumvent intractability and achieve efficient querying and mining of frequent patterns. Some noteworthy papers in this area include: Improved Circular Dictionary Matching, which presents an efficient solution for circular dictionary matching queries within compressed space. Linear-space LCS enumeration with quadratic-time delay for two strings, which proposes an algorithm for exhaustively searching all longest common subsequences in a time-efficient manner using only linear space. Indexing Strings with Utilities, which introduces a natural generalization of the classic String Indexing problem and proposes efficient data structures and algorithms for querying and mining frequent substrings with utilities.

Sources

Improved Circular Dictionary Matching

The Complexity of Maximal Common Subsequence Enumeration

Linear-space LCS enumeration with quadratic-time delay for two strings

Indexing Strings with Utilities

Built with on top of