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 $\mbox{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 $\mbox{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.

Publication
Journal of Discrete Algorithms 34:49-53
Date