.png){kind=icon}
.png){kind=icon}
Return
Efficient Computation of Closed Substrings
.png){kind=icon}
PRE
AI
DOI：10.1007/978-3-032-05228-5_15.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
A closed string u is either of length one or contains a border that occurs only as a prefix and as a suffix in u and nowhere else within u. Inthispaper, wepresent afast O(n log n) time algorithm to compute all O(n(2)) closed substrings by introducing a compact representation for all closed substrings of a string w[1..n], using only O(n log n) space. We also present a simple and space-efficient solution to compute all maximal closed substrings (MCSs) using the suffix array (SA) and the longest common prefix (LCP) array of w[1..n]. Finally, we show that the exactnumberofMCSs(M (f(n))) in a Fibonacci word f(n), for n >= 5, is approximate to (1+ 1/phi(2)) F-n approximate to 1.382F(n), where phi is the golden ratio.
Keywords:
Closed Strings
Maximal Closed Substrings
Fibonacci Words
Journal
S
IF:
0
Papers:
22
Citations:
0