Search

Abstract: A breakthrough in the field of text algorithms was the discovery of the fact that the maximal number of runs in a word of length n is and that they can all be computed in time. We study some applications of this result. New simpler time algorithms are presented for classical textual problems: computing all distinct k-th word powers for a given k, in particular squares for , and finding all local periods in a given word of length n. Additionally, we present an efficient algorithm for testing primitivity of factors of a word and computing their primitive roots. Applications of runs, despite their importance, are underrepresented in existing literature (approximately one page in the paper of Kolpakov and Kucherov, 1999 [25,26]). In this paper we attempt to fill in this gap. We use Lyndon words and introduce the Lyndon structure of runs as a useful tool when computing powers. In problems related to periods we use some versions of the Manhattan skyline problem. [Copyright &y& Elsevier]

Abstract: Three new simple time algorithms related to repeating factors are presented in the paper. The first two algorithms employ only a basic textual data structure called the Dictionary of Basic Factors. Despite their simplicity these algorithms not only detect existence of powers (in particular, squares) in a string but also find all primitively rooted cubes (as well as higher powers) and all cubic runs. Our third time algorithm computes all runs and is probably the simplest known efficient algorithm for this problem. It uses additionally the Longest Common Extension function, however, due to relaxed running time constraints, a simple time implementation can be used. At the cost of logarithmic factor (in time complexity) we obtain novel algorithmic solutions for several classical string problems which are much simpler than (usually quite sophisticated) linear time algorithms. [Copyright &y& Elsevier]

Methods from string and pattern matching have recently been applied to many problems in music retrieval. We consider the so-called lead sheet problem , where symbolic representations of the harmony, melody, and, usually, bass line are presented separately. This is a common situation in some forms of popular music but is also significant for ‘classical’ music in many cases. A number of different but related musical situations are analysed and efficient algorithms are presented for music retrieval in each one. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we study approximate regularities of strings, that is, approximate periods, approximate covers, and approximate seeds. We explore their similarities and differences and we implement algorithms for solving the smallest distance approximate period/cover/seed problem and the restricted smallest approximate period/cover/seed/ problem in polynomial time, under a variety of distance rules (the Hamming distance, the edit distance, and the weighted edit distance). Then, we analyse our experimental results to find out the time complexity of the algorithms in practice. [Copyright &y& Elsevier]

Abstract: The notion of the cover is a generalization of a period of a string, and there are linear time algorithms for finding the shortest cover. The seed is a more complicated generalization of periodicity, it is a cover of a superstring of a given string, and the shortest seed problem is of much higher algorithmic difficulty. The problem is not well understood, no linear time algorithm is known. In the paper we give linear time algorithms for some of its versions—computing shortest left-seed array, longest left-seed array and checking for seeds of a given length. The algorithm for the last problem is used to compute the seed array of a string (i.e., the shortest seeds for all the prefixes of the string) in time. We describe also a simpler alternative algorithm computing efficiently the shortest seeds. As a by-product we obtain an time algorithm checking if the shortest seed has length at least and finding the corresponding seed. We also correct some important details missing in the previously known shortest-seed algorithm Iliopoulos et al. (1996) [14]. [Copyright &y& Elsevier]