Name
Abstract | ||
|---|---|---|
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 ( n 3 h ) time and O ( n 2 ) 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 ( n 3 h + g n h log ¿ N ) time and O ( n 2 ) 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 ( n 2 h ) time and O ( n h ( n + log 2 ¿ N ) ) time, respectively. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.ic.2014.09.009 | Information & Computation |
Keywords | DocType | Volume |
Straight-line programs (SLPs),Runs,Squares,Gapped palindromes,Compressed string processing algorithms | Journal | 240 |
Issue | ISSN | Citations |
C | 0890-5401 | 3 |
PageRank | References | Authors |
0.39 | 13 | 8 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tomohiro I | 1 | 148 | 22.06 |
| Wataru Matsubara | 2 | 52 | 5.87 |
| Kouji Shimohira | 3 | 3 | 0.73 |
| Shunsuke Inenaga | 4 | 595 | 79.02 |
| Hideo Bannai | 5 | 620 | 79.87 |
| Masayuki Takeda | 6 | 902 | 79.24 |
| Kazuyuki Narisawa | 7 | 33 | 6.82 |
| Ayumi Shinohara | 8 | 936 | 88.28 |