Paper accepted at CPM 2021

Paper at CPM 2021 conference


Algorithms for shortest superstring questions

A linear time algorithm for Shortest Cyclic Cover of Strings

Merging words according to their overlap yields a superstring. This basic operation allows to infer long strings from a collection of short pieces, as in genome assembly. To capture a maximum of overlaps, the goal is to infer the shortest superstring …

Reverse engineering of compact suffix trees and links: A novel algorithm

Invented in the 1970s, the Suffix Tree (ST) is a data structure that indexes all substrings of a text in linear space. Although more space demanding than other indexes, the ST remains likely an inspiring index because it represents substrings in a …

Longest common subsequence problem for unoriented and cyclic strings

Given a finite set of strings X, the Longest Common Subsequence problem (LCS) consists in finding a subsequence common to all strings in X that is of maximal length. LCS is a central problem in stringology and finds broad applications in text …