4
$\begingroup$

Let $\Sigma$ be an ordered finite alphabet. Longest Common Extension (LCE) queries are the following problem:

Input: a string $w$ of size $n$
Query: two integers $i$ and $j$ such that $0 < i \leq n$ and $0 < j \leq n$
Output: $\max \{ k, w[i..i+k] = w[j..j+k] \}$

where $w[i]$ is the $i$-th character of $w$ (starting from $1$) and $w[i..j] = w[i] w[i+1] \dots w[j]$.

LCE queries are solvable in $O(1)$ for any $i$ and $j$ after a linear preprocessing of $w$.

I want to solve a variant of this problem (one might call it Mirror LCE queries):

Input (same as before): a string $w$ of size $n$
Query (same as before): two integers $i$ and $j$ such that $0 < i \leq n$ and $0 < j \leq n$
Output : $\{ k, w[i-k..i] = w[j..j+k] \}$

Are Mirror LCE queries enumerable in linear preprocessing constant-delay ?

Note: by linear preprocessing constant-delay, I mean the following: the algorithm is first given $w$ and has linear time to produce a data structure $D$. This data structure can then be used with any $i$ and $j$ to enumerate all the corresponding $k$s with no duplicates with $O(1)$ time between two consecutive answers.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.