Online multiple palindrome pattern matching

Hwee Kim; Yo Sub Han

doi:10.1007/978-3-319-11918-2

Online multiple palindrome pattern matching

Hwee Kim, Yo Sub Han

College of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Citation (Scopus)

Abstract

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 P₁,..., P_k, we study the online multiple palindrome pattern matching problem that finds all pairs of an index i and a pattern P_j such that T [i−|P_j|+1: i] and P_j are pal-equivalent. We solve the problem in O(m_kM) preprocessing time and O(m_kn) query time using O(m_kM) space, where M is the sum of all pattern lengths and m_k is the longest pattern length.

Original language	English
Title of host publication	String Processing and Information Retrieval - 21st International Symposium, SPIRE 2014, Proceedings
Editors	Edleno Moura, Maxime Crochemore
Publisher	Springer Verlag
Pages	173-178
Number of pages	6
ISBN (Electronic)	9783319119175
DOIs	https://doi.org/10.1007/978-3-319-11918-2
Publication status	Published - 2014
Event	21st International Symposium on String Processing and Information Retrieval, SPIRE 2014 - Ouro Preto, Brazil Duration: 2014 Oct 20 → 2014 Oct 22

Publication series

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

Other

Other	21st International Symposium on String Processing and Information Retrieval, SPIRE 2014
Country/Territory	Brazil
City	Ouro Preto
Period	14/10/20 → 14/10/22

Bibliographical note

Publisher Copyright:
© Springer International Publishing Switzerland 2014.

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-319-11918-2

Cite this

Kim, H., & Han, Y. S. (2014). Online multiple palindrome pattern matching. In E. Moura, & M. Crochemore (Eds.), String Processing and Information Retrieval - 21st International Symposium, SPIRE 2014, Proceedings (pp. 173-178). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8799). Springer Verlag. https://doi.org/10.1007/978-3-319-11918-2

Kim, Hwee ; Han, Yo Sub. / Online multiple palindrome pattern matching. String Processing and Information Retrieval - 21st International Symposium, SPIRE 2014, Proceedings. editor / Edleno Moura ; Maxime Crochemore. Springer Verlag, 2014. pp. 173-178 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{96e57ad7c3234dd4b20828d6ea272ef7,

title = "Online multiple palindrome pattern matching",

abstract = "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.",

author = "Hwee Kim and Han, {Yo Sub}",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2014.; 21st International Symposium on String Processing and Information Retrieval, SPIRE 2014 ; Conference date: 20-10-2014 Through 22-10-2014",

year = "2014",

doi = "10.1007/978-3-319-11918-2",

language = "English",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "173--178",

editor = "Edleno Moura and Maxime Crochemore",

booktitle = "String Processing and Information Retrieval - 21st International Symposium, SPIRE 2014, Proceedings",

address = "Germany",

}

Kim, H & Han, YS 2014, Online multiple palindrome pattern matching. in E Moura & M Crochemore (eds), String Processing and Information Retrieval - 21st International Symposium, SPIRE 2014, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8799, Springer Verlag, pp. 173-178, 21st International Symposium on String Processing and Information Retrieval, SPIRE 2014, Ouro Preto, Brazil, 14/10/20. https://doi.org/10.1007/978-3-319-11918-2

Online multiple palindrome pattern matching. / Kim, Hwee; Han, Yo Sub.
String Processing and Information Retrieval - 21st International Symposium, SPIRE 2014, Proceedings. ed. / Edleno Moura; Maxime Crochemore. Springer Verlag, 2014. p. 173-178 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8799).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Online multiple palindrome pattern matching

AU - Kim, Hwee

AU - Han, Yo Sub

N1 - Publisher Copyright: © Springer International Publishing Switzerland 2014.

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84908699284&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84908699284&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-11918-2

DO - 10.1007/978-3-319-11918-2

M3 - Conference contribution

AN - SCOPUS:84908699284

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 173

EP - 178

BT - String Processing and Information Retrieval - 21st International Symposium, SPIRE 2014, Proceedings

A2 - Moura, Edleno

A2 - Crochemore, Maxime

PB - Springer Verlag

T2 - 21st International Symposium on String Processing and Information Retrieval, SPIRE 2014

Y2 - 20 October 2014 through 22 October 2014

ER -

Kim H, Han YS. Online multiple palindrome pattern matching. In Moura E, Crochemore M, editors, String Processing and Information Retrieval - 21st International Symposium, SPIRE 2014, Proceedings. Springer Verlag. 2014. p. 173-178. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-11918-2

Online multiple palindrome pattern matching

Abstract

Publication series

Other

Bibliographical note

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this