?
Sublinear Space Algorithms for the Longest Common Substring Problem
P. 605–617.
Стариковская Т. А., Vildhoj H. W., Kociumaka T.
В книге
Vol. 8737. , Berlin: Springer, 2014.
Ekaterinburg: Ural Fedearal University, 2014.
Добавлено: 17 октября 2014 г.
Артемова Е. Л., , in: Procedia Computer Science. 2nd International Conference on Information Technology and Quantitative Management, ITQM 2014. National Research University Higher School of Economics (HSE) in Moscow (Russia) on June 3-5, 2014Vol. 31.: Amsterdam: Elsevier, 2014. Ch. 22 P. 193–200.
Добавлено: 14 октября 2014 г.
Бабенко М. А., Gawrychowski P., Kociumaka T. и др., , 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 ...
Добавлено: 4 октября 2014 г.
Vildhoj H. W., Стариковская Т. А., , in: Combinatorial Algorithms. 25th International Workshop, IWOCA 2014, Duluth, MN, USA, October 15-17, 2014, Revised Selected PapersVol. 8986.: Springer, 2014. P. 338–350.
In this paper we study the structure of suffix trees. Given an unlabeled tree τ on n nodes and suffix links of its internal nodes, we ask the question “Is τ a suffix tree?”, i.e., is there a string S whose suffix tree has the same topological structure as τ? We place no restrictions on ...
Добавлено: 4 октября 2014 г.
Maxim Babenko, Ignat Kolesnichenko, Стариковская Т. А., Lecture Notes in Computer Science 2013 Vol. 7922 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 ...
Добавлено: 13 ноября 2013 г.
Миркин Б. Г., Артемова Е. Л., , in: Clusters, orders, trees: methods and applications. In Honor of Boris Mirkin's 70th BirthdayVol. 92.: Berlin: Springer, 2014.
Abstract. A suffix-tree based method for measuring similarity of a key phrase to an unstructured text is proposed. The measure involves less computation and it does not depend on the length of the text or the key phrase. This applies to the following tasks in semantic text analysis:
Finding interrelations between key phrases over a set of ...
Добавлено: 4 ноября 2013 г.
Бабенко М. А., Стариковская Т. А., , in: Lecture Notes in Computer ScienceVol. 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 ...
Добавлено: 30 октября 2013 г.
Бабенко М. А., Стариковская Т. А., Проблемы передачи информации 2011 Т. 47 № 1 С. 28–33
Описан алгоритм, решающий задачу нахождения приближенной максимальной общей подстроки двух строк $\alpha_1$ и $\alpha_2$ за время $O(\abs{\alpha_1} \abs{\alpha_2})$ с использованием $O(\abs{\alpha_1})$ дополнительной памяти. При обращении к строке $\alpha_2$ алгоритм читает ее только \emph{слева направо, начиная с первого символа}. Используется RAM-модель вычислений. ...
Добавлено: 30 октября 2013 г.
Vildhoj H. W., Стариковская Т. А., , in: Lecture Notes in Computer ScienceVol. 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 ...
Добавлено: 30 октября 2013 г.
Артемова Е. Л., Чугунова О. Н., Аскарова Ю. А. и др., , in: CDUD – 2010: International Workshop on Concept Discovery in Unstructured Data.: M.: Higher School of Economics Publishing House, 2011. P. 20–31.
Добавлено: 27 декабря 2012 г.