### ?

## Time-Space Trade-Offs for the Longest Common Substring Problem

P. 223-234.

Vildhoj H. W., Starikovskaya T.

Lexicographically minimal and lexicographically maximal suffixes of a string are fundamental notions of stringology. It is well known that the lexicographically minimal and maximal suffixes of a given string $S$ can be computed in linear time and space by constructing a suffix tree or a suffix array of $S$. Here we consider the case when $S$ is a substring of another string $T$ of length $n$. We propose two linear-space data structures for $T$ which allow to compute the minimal suffix of $S$ in $O(\log^{1 + \varepsilon} n)$ time (for any fixed $\varepsilon > 0$) and the maximal suffix of $S$ in $O(\log n)$ time. Both data structures take $O(n)$ time to construct.

### In book

Vol. 7922: Proceedings of the 24th Symposium on Combinatorial Pattern Matching. , Berlin : Springer, 2013

Kucherov G., Nekrich Y., Starikovskaya T., , in : Lecture Notes in Computer Science. Vol. 7608: Proceedings of the 19th International Symposium on String Processing and Information Retrieval.: Berlin : Springer, 2012. P. 307-317.

We study the following three problems of computing generic or discriminating words for a given collection of documents. Given a pattern $P$ and a threshold $d$, we want to report (i) all longest extensions of $P$ which occur in at least $d$ documents, (ii) all shortest extensions of $P$ which occur in less than $d$ ...

Added: October 30, 2013

Babenko M., Kolesnichenko I., Starikovskaya T., , in : Lecture Notes in Computer Science. Vol. 7922: Proceedings of the 24th Symposium on Combinatorial Pattern Matching.: Berlin : Springer, 2013. P. 28-37.

Lexicographically minimal and lexicographically maximal suffixes of a string are fundamental notions of stringology. It is well known that the lexicographically minimal and maximal suffixes of a given string S can be computed in linear time and space by constructing a suffix tree or a suffix array of S. Here we consider the case when ...

Added: October 30, 2013

Babenko M. A., Starikovskaya T., Проблемы передачи информации 2011 Т. 47 № 1 С. 28-33

Описан алгоритм, решающий задачу нахождения приближенной максимальной общей подстроки двух строк $\alpha_1$ и $\alpha_2$ за время $O(\abs{\alpha_1} \abs{\alpha_2})$ с использованием $O(\abs{\alpha_1})$ дополнительной памяти. При обращении к строке $\alpha_2$ алгоритм читает ее только \emph{слева направо, начиная с первого символа}. Используется RAM-модель вычислений. ...

Added: October 30, 2013

Babenko M. A., Starikovskaya T., , in : Lecture Notes in Computer Science. Vol. 5010: Proceedings of the Third International Computer Science Symposium in Russia.: Berlin : Springer, 2008. P. 64-75.

Given a set of $N$ strings $A = \set{\alpha_1, \ldots, \alpha_N}$ of total length $n$ over alphabet~$\Sigma$ one may ask to find, for a fixed integer $K$, $2 \le K \le N$, the longest substring $\beta$ that appears in at least $K$ strings in $A$. It is known that this problem can be solved in ...

Added: October 30, 2013

Kucherov G., Nekrich Y., Starikovskaya T., , in : Lecture Notes in Computer Science. Vol. 7354: Proceedings of the 23rd Symposium on Combinatorial Pattern Matching.: Berlin : Springer, 2012. P. 196-207.

We study a new variant of the string matching problem called {\em cross-document string matching}, which is the problem of indexing a collection of documents to support an efficient search for a pattern in a selected document, where the pattern itself is a substring of another document. Several variants of this problem are considered, ...

Added: October 30, 2013

Babkina T. S., Demidovskij A., Babkin E., International Journal of Big Data Intelligence 2018 Vol. 5 No. 3 P. 143-155

This paper presents two new approaches to solving a classical NP-hard problem of maximum clique problem (MCP), which frequently arises in the domain of information management, including design of database structures and big data processing. In our research, we are focusing on solving that problem using the paradigm of artificial neural networks. The first approach ...

Added: October 3, 2018

Kopelowitz T., Kucherov G., Nekrich Y. et al., Journal of Discrete Algorithms 2013

We study a new variant of the pattern matching problem called cross-document pattern matching, which is the problem of indexing a collection of documents to support an efficient search for a pattern in a selected document, where the pattern itself is a substring of another document. Several variants of this problem are considered, and efficient linear ...

Added: October 30, 2013

Babenko M. A., Gawrychowski P., Kociumaka T. et al., , in : Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. : San Diego : SIAM, 2015. P. 572-591.

We present an improved wavelet tree construction algorithm and discuss its applications to a number of rank/select problems for integer keys and strings. Given a string of length n over an alphabet of size ω ≤ n, our method builds the wavelet tree in O(n log ω √log n) time, improving upon the state-of-the-art algorithm ...

Added: October 4, 2014

Kucherov G., Nekrich Y., Gawrychowski P. et al., , in : Lecture Notes in Computer Science. Vol. 8214: Proceedings of the 20th Symposium on String Processing and Information Retrieval.: Berlin : Springer, 2013. P. 129-140.

We revisit two variants of the problem of computing minimal discriminating words studied in [5]. Given a pattern P and a threshold d, we want to report (i) all shortest extensions of P which occur in less than d documents, and (ii) all shortest extensions of P which occur only in d selected documents. For ...

Added: October 30, 2013

Галимуллин М. Ф., Kalishenko E., Рапоткин Н. А., Известия Санкт-Петербургского государственного электротехнического университета ЛЭТИ 2016 № 7 С. 13-23

Deals with the development of threads synchronizing strategies based on the creation of concurrent «flat-combining» data structures as well as research of their performance. The paper considers «flat-combining» approach and its implementation in the library libcds, the development of thread synchronization strategy and its possible implementations. The efficiency of synchronization strategies usage is researched on ...

Added: November 1, 2018

Starikovskaya T., , in : Lecture Notes in Computer Science. Vol. 7464: Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science.: Berlin : Springer, 2012. P. 789-799.

We present an algorithm which computes the Lempel-Ziv factorization of a word $W$ of length $n$ on an alphabet $\Sigma$ of size $\sigma$ online in the following sense: it reads $W$ starting from the left, and, after reading each $r = O(\log_{\sigma}{n})$ characters of $W$, updates the Lempel-Ziv factorization. The algorithm requires $O(n\log\sigma)$ bits of ...

Added: October 30, 2013

Babenko A., Lempitsky V., , in : Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2012). : Providence : IEEE, 2012. P. 3069-3076.

A new data structure for efficient similarity search in very large dataseis of high-dimensional vectors is introduced. This structure called the inverted multi-index generalizes the inverted index idea by replacing the standard quantization within inverted indices with product quantization. For very similar retrieval complexity and preprocessing time, inverted multi-indices achieve a much denser subdivision of ...

Added: October 1, 2014

Полякова О. А., Пермь : Издательство Пермского национального исследовательского политехнического университета, 2019

The article deals with the application of the basic principles of structured programming in complex programs systems in the high-level language C ++, which are demonstrated on meaningful examples. ...

Added: August 31, 2020

Springer, 2019

16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5–7, 2019, Proceedings ...

Added: October 26, 2021

Vildhoj H. W., Starikovskaya T., , in : Combinatorial Algorithms. 25th International Workshop, IWOCA 2014, Duluth, MN, USA, October 15-17, 2014, Revised Selected Papers. Vol. 8986.: Springer, 2014. P. 338-350.

In this paper we study the structure of suffix trees. Given an unlabelled tree $\tau$ on $n$ nodes and suffix links of its internal nodes, we ask the question "Is $\tau$ a suffix tree?", i.e., is there a string $S$ whose suffix tree has the same topological structure as $\tau$? We place no restrictions on ...

Added: October 4, 2014

Edward Elgar Publishing, 2019

The digital economy is gradually gaining traction through a variety of recent technological developments, including the introduction of the Internet of things, artificial intelligence and markets for data. This innovative book contains contributions from leading competition law scholars who map out and investigate the anti-competitive effects that are developing in the digital economy. ...

Added: August 4, 2020

Voskov L., Efremov S. G., В кн. : Distributed computer and communication networks: control, computation, communications (DCCN-2013). : М. : Техносфера, 2013. С. 197-199.

In this paper we propose models and algorithms for increasing lifetime of dynamically reconfigurable wireless sensor networks with a mobile sink and anonymous power supplies. A new definition and assessment model of a network lifetime in case of dynamic reconfiguration are given. We propose a new method for dynamic reconfiguration aimed at finding an optimal ...

Added: February 12, 2014

Ulyanov M.V., Fomichev M.I., Business Informatics 2015 No. 4 (34) P. 38-46

The resource efficiency of different implementations of the branch-and-bound method for the classical traveling salesman problem depends, inter alia, on ways to organize a search decision tree generated by this method. The classic «time-memory» dilemma is realized herein either by an option of storing reduced matrices at the points of the decision tree, which leads ...

Added: November 5, 2016

Bliznets Ivan, Cygan M., Komosa P. et al., , in : Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. : SIAM, 2016. P. 1132-1151.

In this work, we focus on several completion problems for subclasses of chordal graphs: Minimum Fill-In, Interval Completion, Proper IntervalCompletion, Threshold Completion, and Trivially Perfect Completion. In these problems, the task is to add at most k edges to a given graph in order to obtain a chordal, interval, proper interval, threshold, or trivially perfect graph, respectively. We prove the following lower bounds ...

Added: October 31, 2018

Springer, 2020

This special issue of Theory of Computing Systems consists of extended journal papers originally presented at the 13th International Computer Science Symposium in Russia (CSR 2018) held on June 6–10, 2018 in Moscow, Russia. The event was hosted by National Research University Higher School of Economics and chaired by Vladimir V. Podolskii. Preliminary versions of ...

Added: October 27, 2020

Соколов Б. В., Ivanov D., Dolgui A., Algorithms 2018 Vol. 11 No. 5 P. 57

Added: February 11, 2020

M. Polyakova, Semenov A. V., Kovalyuk V. et al., IEEE Transactions on Applied Superconductivity 2019 Vol. 29 No. 5 P. 1-5

We present a simple quantum detector tomography
protocol, which allows, without ambiguities, to measure the twospot
detection efficiency and extract the hot-spot interaction length
of SNSPDs with unity intrinsic detection efficiency. We identify a
significant parasitic contribution to the measured two-spot efficiency,
related to an effect of the bias circuit, and find a way to rule
out this contribution during data ...

Added: October 23, 2019

МГУ, МАКС Пресс, 2018

The proceedings of the tenth international conference "Discrete Models in Control Systems Theory" (Moscow and Moscow Region, May 23-25, 2018) includes 100 papers on such topics as discrete functional systems, properties of discrete functions, synthesis and complexity of control systems, reliability, control and diagnostics of control systems, automata, graph theory, combinatorics, coding theory, mathematical methods ...

Added: June 14, 2018