5 citations · 6 across the 5 of their papers we have counts for
7 papers
Maximal Unbordered Factors of Random Strings
Patrick Hagge Cording, Travis Gagie, Mathias Bæk Tejs Knudsen +1
A border of a string is a non-empty prefix of the string that is also a suffix of the string, and a string is unbordered if it has no border other than itself. Loptev, Kucherov, an…
Finger Search in Grammar-Compressed Strings
Philip Bille, Anders Roy Christiansen, Patrick Hagge Cording +1
Grammar-based compression, where one replaces a long string by a small context-free grammar that generates the string, is a simple and powerful paradigm that captures many popular…
Dynamic Relative Compression, Dynamic Partial Sums, and Substring Concatenation
Philip Bille, Patrick Hagge Cording, Inge Li Gørtz +3
Given a static reference string and a source string , a relative compression of with respect to is an encoding of as a sequence of references to substrings of $R…
Optimal Time Random Access to Grammar-Compressed Strings in Small Space
Patrick Hagge Cording
The random access problem for compressed strings is to build a data structure that efficiently supports accessing the character in position of a string given in compressed form…
Compressed Subsequence Matching and Packed Tree Coloring
Philip Bille, Patrick Hagge Cording, Inge Li Gørtz
We present a new algorithm for subsequence matching in grammar compressed strings. Given a grammar of size compressing a string of size and a pattern string of size ove…
Fingerprints in Compressed Strings
Philip Bille, Patrick Hagge Cording, Inge Li Gørtz +3
The Karp-Rabin fingerprint of a string is a type of hash value that due to its strong properties has been used in many string algorithms. In this paper we show how to construct a d…
Compact q-gram Profiling of Compressed Strings
Philip Bille, Patrick Hagge Cording, Inge Li Gørtz
We consider the problem of computing the q-gram profile of a string \str of size compressed by a context-free grammar with production rules. We present an algorithm that ru…