Source author record

Mikhail Rubinchik

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 Formal Languages and Automata Theory math.CO

Catalog footprint

Research overview

5works

3topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Palindromic k-Factorization in Pure Linear Time

Given a string $s$ of length $n$ over a general alphabet and an integer $k$ , the problem is to decide whether $s$ is a concatenation of $k$ nonempty palindromes. Two previously known solutions for this problem work in time $O(kn)$ and $O(n\log n)$ respectively. Here we settle the complexity of this problem in the word-RAM model, presenting an $O(n)$ -time online deciding algorithm. The algorithm simultaneously finds the minimum odd number of factors and the minimum even number of factors in a factorization of a string into nonempty palindromes. We also demonstrate how to get an explicit factorization of $s$ into $k$ palindromes with an $O(n)$ -time offline postprocessing.

preprint2015arXiv

$\mathrm{Pal}^k$ Is Linear Recognizable Online

Given a language $L$ that is online recognizable in linear time and space, we construct a linear time and space online recognition algorithm for the language $L\cdot\mathrm{Pal}$ , where $\mathrm{Pal}$ is the language of all nonempty palindromes. Hence for every fixed positive $k$ , $\mathrm{Pal}^k$ is online recognizable in linear time and space. Thus we solve an open problem posed by Galil and Seiferas in 1978.

preprint2015arXiv

EERTREE: An Efficient Data Structure for Processing Palindromes in Strings

We propose a new linear-size data structure which provides a fast access to all palindromic substrings of a string or a set of strings. This structure inherits some ideas from the construction of both the suffix trie and suffix tree. Using this structure, we present simple and efficient solutions for a number of problems involving palindromes.

preprint2015arXiv

The Number of Distinct Subpalindromes in Random Words

We prove that a random word of length $n$ over a $k$ -ary fixed alphabet contains, on expectation, $Θ(\sqrt{n})$ distinct palindromic factors. We study this number of factors, $E(n,k)$ , in detail, showing that the limit $\lim_{n\to\infty}E(n,k)/\sqrt{n}$ does not exist for any $k\ge2$ , $\liminf_{n\to\infty}E(n,k)/\sqrt{n}=Θ(1)$ , and $\limsup_{n\to\infty}E(n,k)/\sqrt{n}=Θ(\sqrt{k})$ . Such a complicated behaviour stems from the asymmetry between the palindromes of even and odd length. We show that a similar, but much simpler, result on the expected number of squares in random words holds. We also provide some experimental data on the number of palindromic factors in random words.

preprint2013arXiv

Finding Distinct Subpalindromes Online

We exhibit an online algorithm finding all distinct palindromes inside a given string in time $Θ(n\log|Σ|)$ over an ordered alphabet and in time $Θ(n|Σ|)$ over an unordered alphabet. Using a reduction from a dictionary-like data structure, we prove the optimality of this algorithm in the comparison-based computation model.

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.

Mikhail Rubinchik

Research overview

Is this your work?

5 publications

Palindromic k-Factorization in Pure Linear Time

$\mathrm{Pal}^k$ Is Linear Recognizable Online

EERTREE: An Efficient Data Structure for Processing Palindromes in Strings

The Number of Distinct Subpalindromes in Random Words

Finding Distinct Subpalindromes Online

See the researcher in context

Building this map preview

Mikhail Rubinchik

Research overview

Is this your work?

5 publications

Palindromic k-Factorization in Pure Linear Time

Palk\mathrm{Pal}^kPalk Is Linear Recognizable Online

EERTREE: An Efficient Data Structure for Processing Palindromes in Strings

The Number of Distinct Subpalindromes in Random Words

Finding Distinct Subpalindromes Online

See the researcher in context

Building this map preview

$\mathrm{Pal}^k$ Is Linear Recognizable Online