ISSN:
1432-0541
Keywords:
Combinatorial algorithms on words
;
String algorithms
;
Periodicity of strings
;
Covering of strings
;
Partitioning
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract We consider the problem of finding the repetitive structures of a given stringx. The periodu of the stringx grasps the repetitiveness ofx, sincex is a prefix of a string constructed by concatenations ofu. We generalize the concept of repetitiveness as follows: A stringw covers a stringx if there is a superstring ofx which is constructed by concatenations and superpositions ofw. A substringw ofx is called aseed ofx ifw coversx. We present anO(n logn)-time algorithm for finding all the seeds of a given string of lengthn.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01955677
Permalink