Source author record

Tomasz Walen

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Discrete Mathematics Formal Languages and Automata Theory

Catalog footprint

Research overview

4works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2013arXiv

Order-Preserving Suffix Trees and Their Algorithmic Applications

Recently Kubica et al. (Inf. Process. Let., 2013) and Kim et al. (submitted to Theor. Comp. Sci.) introduced order-preserving pattern matching. In this problem we are looking for consecutive substrings of the text that have the same "shape" as a given pattern. These results include a linear-time order-preserving pattern matching algorithm for polynomially-bounded alphabet and an extension of this result to pattern matching with multiple patterns. We make one step forward in the analysis and give an $O(\frac{n\log{n}}{\log\log{n}})$ time randomized algorithm constructing suffix trees in the order-preserving setting. We show a number of applications of order-preserving suffix trees to identify patterns and repetitions in time series.

preprint2011arXiv

Efficient Seeds Computation Revisited

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 $O(n^2)$ time. We describe also a simpler alternative algorithm computing efficiently the shortest seeds. As a by-product we obtain an $O(n\log{(n/m)})$ time algorithm checking if the shortest seed has length at least $m$ and finding the corresponding seed. We also correct some important details missing in the previously known shortest-seed algorithm (Iliopoulos et al., 1996).

preprint2010arXiv

On the maximal sum of exponents of runs in a string

A run is an inclusion maximal occurrence in a string (as a subinterval) of a repetition $v$ with a period $p$ such that $2p \le |v|$ . The exponent of a run is defined as $|v|/p$ and is $\ge 2$ . We show new bounds on the maximal sum of exponents of runs in a string of length $n$ . Our upper bound of $4.1n$ is better than the best previously known proven bound of $5.6n$ by Crochemore & Ilie (2008). The lower bound of $2.035n$ , obtained using a family of binary words, contradicts the conjecture of Kolpakov & Kucherov (1999) that the maximal sum of exponents of runs in a string of length $n$ is smaller than $2n$

preprint2009arXiv

On the maximal number of cubic subwords in a string

We investigate the problem of the maximum number of cubic subwords (of the form $www$ ) in a given word. We also consider square subwords (of the form $ww$ ). The problem of the maximum number of squares in a word is not well understood. Several new results related to this problem are produced in the paper. We consider two simple problems related to the maximum number of subwords which are squares or which are highly repetitive; then we provide a nontrivial estimation for the number of cubes. We show that the maximum number of squares $xx$ such that $x$ is not a primitive word (nonprimitive squares) in a word of length $n$ is exactly $\lfloor \frac{n}{2}\rfloor - 1$ , and the maximum number of subwords of the form $x^k$ , for $k\ge 3$ , is exactly $n-2$ . In particular, the maximum number of cubes in a word is not greater than $n-2$ either. Using very technical properties of occurrences of cubes, we improve this bound significantly. We show that the maximum number of cubes in a word of length $n$ is between $(1/2)n$ and $(4/5)n$ . (In particular, we improve the lower bound from the conference version of the paper.)

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.