A note on the longest common compatible prefix problem for partial words

Abstract

For a partial word w the longest common compatible prefix of two positions $i$, $j$, denoted $\text{lccp}(i,j)$, is the largest $k$ such that $w[i,i+k-1]$ and $w[j,j+k-1]$ are compatible. The LCCP problem is to preprocess a partial word in such a way that any query $\text{lccp}(i,j)$ about this word can be answered in $O(1)$ time. We present a simple solution to this problem that works for any linearly-sortable alphabet. Our preprocessing is in time $O(n\mu +n)$, where $\mu$ is the number of blocks of holes in w.