Palindrome Recognition In The Streaming Model
  • FENS
  • Palindrome Recognition In The Streaming Model

You are here

Title: Palindrome Recognition In The Streaming Model

Speaker: Funda Ergun

Date/Time: 24 Jun Wednesday  2015, 14:40 - 15:15

Place: FENS 2019

Bio: A palindrome is defined as a string which reads forwards the same as backwards, such as the string “racecar”.  In this talk we discuss the problem of locatinging the longest (or close to the longest) palindrome in a given data stream of length n, under strict space bounds. We explore the problem in the streaming context, i.e., the algorithm reads the input stream from left to right, using o(n) space, and at the end outputs the location of the longest palindrome, or a palindrome whose length is a small factor away from the length of the longest palindrome. We discuss several randomized algorithms; we show how to compute the location of palindromes whose length is an additive  epsilon approximation to that of the longest palindrome in O(sqrt(n)) space as well as a multiplicative approximation in O(log(n)) space. We also briefly discuss the exact solution to the longest palindrome problem as well as lower bounds showing that our solutions are tight. This is joint work with P. Berenbrink, F. Mallmann-Trenn, E. Sadeqi-Azer.