11 citations · 22 across the 4 of their papers we have counts for
6 papers
Distance Labeling for Families of Cycles
Arseny M. Shur, Mikhail Rubinchik
For an arbitrary finite family of graphs, the distance labeling problem asks to assign labels to all nodes of every graph in the family in a way that allows one to recover the dist…
Palindromic k-Factorization in Pure Linear Time
Mikhail Rubinchik, Arseny M. Shur
Given a string of length over a general alphabet and an integer , the problem is to decide whether is a concatenation of nonempty palindromes. Two previously kno…
EERTREE: An Efficient Data Structure for Processing Palindromes in Strings
Mikhail Rubinchik, Arseny M. Shur
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…
The Number of Distinct Subpalindromes in Random Words
Mikhail Rubinchik, Arseny M. Shur
We prove that a random word of length over a -ary fixed alphabet contains, on expectation, distinct palindromic factors. We study this number of factors, $E(n,…
Is Linear Recognizable Online
Dmitry Kosolobov, Mikhail Rubinchik, Arseny M. Shur
Given a language that is online recognizable in linear time and space, we construct a linear time and space online recognition algorithm for the language ,…
Finding Distinct Subpalindromes Online
Dmitry Kosolobov, Mikhail Rubinchik, Arseny M. Shur
We exhibit an online algorithm finding all distinct palindromes inside a given string in time over an ordered alphabet and in time over an unordered alphabe…