Online multiple palindrome pattern matching

Hwee Kim, Yo Sub Han

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)


A palindrome is a string that reads the same forward and backward. We say that two strings of the same length are pal-equivalent if for each possible center they have the same length of the maximal palindrome. Given a text T of length n and a set of patterns P1,..., Pk, we study the online multiple palindrome pattern matching problem that finds all pairs of an index i and a pattern Pj such that T [i−|Pj|+1: i] and Pj are pal-equivalent. We solve the problem in O(mkM) preprocessing time and O(mkn) query time using O(mkM) space, where M is the sum of all pattern lengths and mk is the longest pattern length.

Original languageEnglish
Title of host publicationString Processing and Information Retrieval - 21st International Symposium, SPIRE 2014, Proceedings
EditorsEdleno Moura, Maxime Crochemore
PublisherSpringer Verlag
Number of pages6
ISBN (Electronic)9783319119175
Publication statusPublished - 2014
Event21st International Symposium on String Processing and Information Retrieval, SPIRE 2014 - Ouro Preto, Brazil
Duration: 2014 Oct 202014 Oct 22

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other21st International Symposium on String Processing and Information Retrieval, SPIRE 2014
CityOuro Preto

Bibliographical note

Publisher Copyright:
© Springer International Publishing Switzerland 2014.

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Online multiple palindrome pattern matching'. Together they form a unique fingerprint.

Cite this