Covering a string |
| |
Authors: | C S Iliopoulos D W G Moore K Park |
| |
Affiliation: | (1) Department of Computer Science, King's College London, Strand, London, England;(2) School of Computing, Curtin University, Perth, WA, Australia;(3) Department of Computer Engineering, Seoul National University, 151-742 Seoul, Korea |
| |
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.Partially supported by SERC Grants GR/F 00898 and GR/J 17844, NATO Grant CRG 900293, ESPRIT BRA Grant 7131 for ALCOMII, and MRC Grant G 9115730.Partially supported by MRC Grant G 9115730 and S.N.U. Posco Research Fund 94-15-1112. |
| |
Keywords: | Combinatorial algorithms on words String algorithms Periodicity of strings Covering of strings Partitioning |
本文献已被 SpringerLink 等数据库收录! |
|