TY - GEN

T1 - A Faster longest common extension algorithm on compressed strings and its applications

T2 - 19th Prague Stringology Conference, PSC 2015

AU - Inenaga, Shunsuke

N1 - Publisher Copyright:
© Czech Technical University in Prague, Czech Republic.

PY - 2015

Y1 - 2015

N2 - In this talk, we introduce our recent data structure for longest common extension (LCE) queries on grammar-compressed strings. Our preprocessing input is a straight-line program (SLP) of size n describing a string w of length N, which is essentially a CFG in the Chomsky normal form generating only w. We can preprocess the input SLP in O(n log log n logN log N) time so that later, given two variables and two positions in the strings derived by the variables, we can answer the corresponding LCE query in O(logN log N) time. Our LCE data structure requires O(z logN log N) words of space, where z is the size of the Lempel-Ziv 77 factorization of w. We also show several applications of our LCE data structure on SLPs.

AB - In this talk, we introduce our recent data structure for longest common extension (LCE) queries on grammar-compressed strings. Our preprocessing input is a straight-line program (SLP) of size n describing a string w of length N, which is essentially a CFG in the Chomsky normal form generating only w. We can preprocess the input SLP in O(n log log n logN log N) time so that later, given two variables and two positions in the strings derived by the variables, we can answer the corresponding LCE query in O(logN log N) time. Our LCE data structure requires O(z logN log N) words of space, where z is the size of the Lempel-Ziv 77 factorization of w. We also show several applications of our LCE data structure on SLPs.

UR - http://www.scopus.com/inward/record.url?scp=84978492375&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84978492375&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84978492375

T3 - Proceedings of the Prague Stringology Conference 2015, PSC 2015

SP - 1

EP - 4

BT - Proceedings of the Prague Stringology Conference 2015, PSC 2015

A2 - Zd'arek, Jan

A2 - Holub, Jan

PB - Prague Stringology Club

Y2 - 24 August 2015 through 26 August 2015

ER -