SPIRE

We show how to chain *maximal exact matches* (MEMs) between a query string $Q$ and a labeled directed acyclic graph (DAG) $G=(V,E)$ to solve the *longest common subsequence* (LCS) problem between $Q$ and $G$.

New Repetition-Aware Compressed Suffix Tree. Slightly larger than state-of-the-art, but outperforms them in time, often by orders of magnitude.