1 Search Results for "Katsura, Takashi"

Document
DOI: 10.4230/LIPIcs.CPM.2017.8
Position Heaps for Parameterized Strings

Authors: Diptarama Diptarama, Takashi Katsura, Yuhei Otomo, Kazuyuki Narisawa, and Ayumi Shinohara

Published in: LIPIcs, Volume 78, 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)

Abstract
We propose a new indexing structure for parameterized strings, called parameterized position heap. Parameterized position heap is applicable for parameterized pattern matching problem, where the pattern matches a substring of the text if there exists a bijective mapping from the symbols of the pattern to the symbols of the substring. We propose an online construction algorithm of parameterized position heap of a text and show that our algorithm runs in linear time with respect to the text size. We also show that by using parameterized position heap, we can find all occurrences of a pattern in the text in linear time with respect to the product of the pattern size and the alphabet size.
Cite as

Diptarama Diptarama, Takashi Katsura, Yuhei Otomo, Kazuyuki Narisawa, and Ayumi Shinohara. Position Heaps for Parameterized Strings. In 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 78, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{diptarama_et_al:LIPIcs.CPM.2017.8,
  author =	{Diptarama, Diptarama and Katsura, Takashi and Otomo, Yuhei and Narisawa, Kazuyuki and Shinohara, Ayumi},
  title =	{{Position Heaps for Parameterized Strings}},
  booktitle =	{28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)},
  pages =	{8:1--8:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-039-2},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{78},
  editor =	{K\"{a}rkk\"{a}inen, Juha and Radoszewski, Jakub and Rytter, Wojciech},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2017.8},
  URN =		{urn:nbn:de:0030-drops-73396},
  doi =		{10.4230/LIPIcs.CPM.2017.8},
  annote =	{Keywords: string matching, indexing structure, parameterized pattern matching, position heap}
}
  • Refine by Author
  • 1 Diptarama, Diptarama
  • 1 Katsura, Takashi
  • 1 Narisawa, Kazuyuki
  • 1 Otomo, Yuhei
  • 1 Shinohara, Ayumi

  • Refine by Classification

  • Refine by Keyword
  • 1 indexing structure
  • 1 parameterized pattern matching
  • 1 position heap
  • 1 string matching

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact