کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
426422 | 686058 | 2015 | 16 صفحه PDF | دانلود رایگان |
We address the problems of detecting and counting various forms of regularities in a string represented as a straight-line program (SLP) which is essentially a context free grammar in the Chomsky normal form. Given an SLP of size n that represents a string s of length N, our algorithm computes all runs and squares in s in O(n3h)O(n3h) time and O(n2)O(n2) space, where h is the height of the derivation tree of the SLP. We also show an algorithm to compute all gapped-palindromes in O(n3h+gnhlogN)O(n3h+gnhlogN) time and O(n2)O(n2) space, where g is the length of the gap. As one of the main components of the above solution, we propose a new technique called approximate doubling which seems to be a useful tool for a wide range of algorithms on SLPs. Indeed, we show that the technique can be used to compute the periods and covers of the string in O(n2h)O(n2h) time and O(nh(n+log2N))O(nh(n+log2N)) time, respectively.
Journal: Information and Computation - Volume 240, February 2015, Pages 74–89