License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2014.149
URN: urn:nbn:de:0030-drops-44544
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4454/
Go to the corresponding LIPIcs Volume Portal

Berenbrink, Petra ; Ergün, Funda ; Mallmann-Trenn, Frederik ; Sadeqi Azer, Erfan

Palindrome Recognition In The Streaming Model

pdf-format:
12.pdf (0.8 MB)

Abstract

A palindrome is defined as a string which reads forwards the same as backwards, like, for example, the string "racecar". In the Palindrome Problem, one tries to find all palindromes in a given string. In contrast, in the case of the Longest Palindromic Substring Problem, the goal is to find an arbitrary one of the longest palindromes in the string.

In this paper we present three algorithms in the streaming model for the the above problems, where at any point in time we are only allowed to use sublinear space. We first present a one-pass randomized algorithm that solves the Palindrome Problem. It has an additive error and uses square root of n space. We also give two variants of the algorithm which solve related and practical problems. The second algorithm determines the exact locations of all longest palindromes using two passes and square root of n space. The third algorithm is a one-pass randomized algorithm, which solves the Longest Palindromic Substring Problem. It has a multiplicative error using only O(log(n)) space.

BibTeX - Entry

@InProceedings{berenbrink_et_al:LIPIcs:2014:4454,
  author =	{Petra Berenbrink and Funda Erg{\"u}n and Frederik Mallmann-Trenn and Erfan Sadeqi Azer},
  title =	{{Palindrome Recognition In The Streaming Model}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{149--161},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Ernst W. Mayr and Natacha Portier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4454},
  URN =		{urn:nbn:de:0030-drops-44544},
  doi =		{10.4230/LIPIcs.STACS.2014.149},
  annote =	{Keywords: Palindromes, Streaming Model, Complementary Palindrome}
}

Keywords: Palindromes, Streaming Model, Complementary Palindrome
Collection: 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Issue Date: 2014
Date of publication: 05.03.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI