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.


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.