Finding Distinct Subpalindromes Online / Kosolobov Dmitry,Rubinchik Mikhail,Shur Arseny M. // . - 2013. - V. , l. . - P. 63-69.

ISSN/EISSN:

нет данных / нет данных

Type:

Proceedings Paper

Abstract:

We exhibit an online algorithm finding all distinct palindromes inside a given string in time Theta(n log | Sigma |) over an ordered alphabet and in time Theta(n| Sigma |) over an unordered alphabet. Using a reduction from a dictionary-like data structure, we prove the optimality of this algorithm in the comparison-based computation model.

Author keywords:

stringology; counting palindromes; subpalindromes; palindromic closure; online algorithm STURMIAN WORDS; LINEAR-TIME; PALINDROMES

DOI:

нет данных

Web of Science ID:

ISI:000396440400006

Соавторы в МНС:

—

Другие поля

Поле	Значение
Editor	Holub, J and Zdarek, J
Booktitle	PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2013
Note	8th Prague Stringology Conference (PSC), Czech Tech Univ, Prague, CZECH REPUBLIC, SEP 02-04, 2013
Publisher	CZECH TECHNICAL UNIV PRAGUE
Address	ZIKOVA 4, PRAGUE 6 166 35, CZECH REPUBLIC
Language	English
ISBN	978-80-01-05330-0
Keywords-Plus	STURMIAN WORDS; LINEAR-TIME; PALINDROMES
Research-Areas	Computer Science
Web-of-Science-Categories	Computer Science, Theory \& Methods
Author-Email	dkosolobov@mail.ru mikhail.rubinchik@gmail.com arseny.shur@usu.ru
Number-of-Cited-References	8
Doc-Delivery-Number	BH0TH