2022/01/26 by Lifshits, Yury
#Compressed text #Pattern matching
paper · doi:10.4230/dagsemproc.06201.7
How to solve string problems, if instead of input string we get only program generating it? Is it possible to solve problems faster than just "generate text + apply classical algorithm"? In this paper we consider strings generated by straight-line programs (SLP). These are programs using only assignment operator. We show new algorithms for equivalence, pattern matching, finding periods and covers, computing fingerprint table on SLP-generated strings. From the other hand, computing the Hamming distance is NP-hard. Main corollary is an O(n2*m) algorithm for pattern matching in LZ-compressed texts.