Zobrazeno 1 - 4
of 4
pro vyhledávání: '"Mikhail Rubinchik"'
Autor:
Mikhail Rubinchik, Arseny M. Shur
Publikováno v:
String Processing and Information Retrieval ISBN: 9783319674278
SPIRE
SPIRE
We propose a data structure and an online algorithm to report the number of distinct palindromes in any substring of an input string. Assume that the string S of length n arrives symbol-by-symbol and every symbol is followed by zero or more queries o
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::5e4129a7ab59a8a7ebe53b45ee64f823
https://doi.org/10.1007/978-3-319-67428-5_25
https://doi.org/10.1007/978-3-319-67428-5_25
Autor:
Arseny M. Shur, Mikhail Rubinchik
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783319295152
IWOCA
Lect. Notes Comput. Sci.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Eur. J. Comb.
European Journal of Combinatorics
IWOCA
Lect. Notes Comput. Sci.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Eur. J. Comb.
European Journal of Combinatorics
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 struc
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::82c7dd64844b0e8f372b3f18074300e6
https://doi.org/10.1007/978-3-319-29516-9_27
https://doi.org/10.1007/978-3-319-29516-9_27
Autor:
Mikhail Rubinchik, Arseny M. Shur
Publikováno v:
Fundam Inf
Fundamenta Informaticae
Fundamenta Informaticae
We prove that a random word of length $n$ over a $k$-ary fixed alphabet contains, on expectation, $\Theta(\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)/\
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4a980900d1cdcc8811bd16a551f92ab9
http://arxiv.org/abs/1505.08043
http://arxiv.org/abs/1505.08043
Publikováno v:
Lect. Notes Comput. Sci.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Lecture Notes in Computer Science ISBN: 9783662460771
SOFSEM
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Lecture Notes in Computer Science ISBN: 9783662460771
SOFSEM
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・Pal, where Pal is the language of all nonempty palindromes. Hence for every fixed positive
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a91bf66ba82ccfb3b877889317272f0b
http://arxiv.org/pdf/1404.5244.pdf
http://arxiv.org/pdf/1404.5244.pdf