Analysis of Repetitions in a String
Date Issued
2007
Date
2007
Author(s)
Hong, Jin-Ju
DOI
en-US
Abstract
A repetition is the concatenation of two or more copies of a non-empty string. In particular, a square is the concatenation of two identical non-empty string. Detecting repetitions in a string is a classical problem and has a large variety of applications in many areas such as combinatorics, string algorithms, automata and formal language theory, data compression, music information retrieval, computational molecular biology, etc. The study of square-free strings dates back to the beginning of the last century. In 1980's, several off-line algorithms for determining whether or not a string contains a square were proposed.
Recently, the on-line version of the square detection problem has been studied. In this dissertation, we presented an algorithm to solve the problem. The algorithm is time-optimal either over a general alphabet or over a constant-size alphabet. Further, we solved the on-line repetition detection problem with the same time complexity.
In many applications, fractional repetitions, i.e., periodic substrings, were concerned. It was proved that the number of maximal periodic substring in a string of length n is O(n). The only known result showing the explicit constant coefficient was 4.9812n. We improved the upper bound to 3.9423n.
Subjects
重複字串
偵測
線上
演算法
週期
repetition
square
on-line
detection
string algorithm
f-factorization
suffix trees
maximal periodicity
run
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-96-D89922010-1.pdf
Size
23.31 KB
Format
Adobe PDF
Checksum
(MD5):aa900108b412743f9483645b02f3084d