?
On Minimal and Maximal Suffixes of a Substring
P. 28-37.
Babenko M., Kolesnichenko I., 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+\epsilon} n)$ time (for any $\epsilon > 0$) and the maximal suffix of S in $O(log n)$ time.
In book
Vol. 7922: Proceedings of the 24th Symposium on Combinatorial Pattern Matching. , Berlin : Springer, 2013
Vildhoj H. W., Starikovskaya T., , in : Lecture Notes in Computer Science. Vol. 7922: Proceedings of the 24th Symposium on Combinatorial Pattern Matching.: Berlin : Springer, 2013. P. 223-234.
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
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
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
Springer, 2019
16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5–7, 2019, Proceedings ...
Added: October 26, 2021
Полякова О. А., Пермь : Издательство Пермского национального исследовательского политехнического университета, 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
Babenko M. A., Kociumaka T., Gawrychowski P. et al., , in : Lecture Notes in Computer Science. Vol. 8486: Proceedings of the 25th Annual Symposium on Combinatorial Pattern Matching.: Springer, 2014. P. 30-39.
We revisit the problems of computing the maximal and the minimal non-empty suffixes of a substring of a longer text of length n, introduced by Babenko, Kolesnichenko and Starikovskaya [CPM’13]. For the minimal suffix problem we show that for any 1 ≤ τ ≤ logn there exists a linear-space data structure with(τ)query time and(nlogn/τ)preprocessing time. As a sample application, we show that ...
Added: June 24, 2014
Галимуллин М. Ф., 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
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
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
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
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
Maxim Babenko, Gawrychowski P., Kociumaka T. et al., Theoretical Computer Science 2016 Vol. 638 P. 112-121
We consider the problems of computing the maximal and the minimal non-empty suffixes of substrings of a longer text of length . n. For the minimal suffix problem we show that for every . τ, . 1≤τ≤logn, there exists a linear-space data structure with . O(τ) query time and . O(nlogn/τ) preprocessing time. As a ...
Added: October 8, 2015
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
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
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
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
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
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
Diskin E., Закон 2024 № 1 С. 26-40
The issue of the protection of legitimate rights of personas who were defamed is not new in Russian legal science. The problem of protection of honor and dignity was known to classical Roman law, was the subject of study of pre-revolutionary and Soviet lawyers. However, the classic civilistic constructions formulated in the Civil Code were ...
Added: January 30, 2024
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
Соколов Б. В., Ivanov D., Dolgui A., Algorithms 2018 Vol. 11 No. 5 P. 57
Added: February 11, 2020
Kolpakov R. M., Kucherov G., Starikovskaya T., , in : Proceedings of the First International Conference on Data Compression, Communications and Processing. : NY : IEEE Computer Society, 2013. P. 92-97.
We consider a compact text index based on evenly spaced sparse suffix trees of a text \cite{KU-96}. Such a tree is defined by partitioning the text into blocks of equal size and constructing the suffix tree only for those suffixes that start at block boundaries. We propose a new pattern matching algorithm on this structure. ...
Added: October 30, 2013
Карташева А. А., Философские проблемы информационных технологий и киберпространства 2024
The problem of confirming the authenticity of works of art is especially acute in the digital environment. The issue of authentication is central to both intellectual property law and cultural communication strategies. Originality is a necessary parameter for a work to be recognized as original. Although the concept of «originality» is not enshrined in legal acts, it is an important element for the construction of «authenticity», which is often produced by «cultural intermediaries». The latter can be not only ...
Added: November 30, 2023