English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

A Longest Common Extension (LCE) query on a text $T$ of length $N$ asks forthe length of the longest common prefix of suffixes starting at given twopositions. We show that the signature encoding $\mathcal{G}$ of size $w =O(\min(z \log N \log^* M, N))$ [Mehlhorn et al., Algorithmica 17(2):183-198,1997] of $T$, which can be seen as a compressed representation of $T$, has acapability to support LCE queries in $O(\log N + \log \ell \log^* M)$ time,where $\ell$ is the answer to the query, $z$ is the size of the Lempel-Ziv77(LZ77) factorization of $T$, and $M \geq 4N$ is an integer that can be handledin constant time under word RAM model. In compressed space, this is the fastestdeterministic LCE data structure in many cases. Moreover, $\mathcal{G}$ can beenhanced to support efficient update operations: After processing $\mathcal{G}$in $O(w f_{\mathcal{A}})$ time, we can insert/delete any (sub)string of length$y$ into/from an arbitrary position of $T$ in $O((y+ \log N\log^* M)f_{\mathcal{A}})$ time, where $f_{\mathcal{A}} = O(\min \{ \frac{\log\log M\log\log w}{\log\log\log M}, \sqrt{\frac{\log w}{\log\log w}} \})$. This yieldsthe first fully dynamic LCE data structure. We also present efficientconstruction algorithms from various types of inputs: We can construct$\mathcal{G}$ in $O(N f_{\mathcal{A}})$ time from uncompressed string $T$; in$O(n \log\log n \log N \log^* M)$ time from grammar-compressed string $T$represented by a straight-line program of size $n$; and in $O(z f_{\mathcal{A}}\log N \log^* M)$ time from LZ77-compressed string $T$ with $z$ factors. On topof the above contributions, we show several applications of our data structureswhich improve previous best known results on grammar-compressed stringprocessing.

Fully dynamic data structure for LCE queries in compressed space