Document Open Access Logo

Faster Queries for Longest Substring Palindrome After Block Edit

Authors Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai , Masayuki Takeda

PDF
Thumbnail PDF

File

LIPIcs.CPM.2019.27.pdf
  • Filesize: 0.67 MB
  • 13 pages

Document Identifiers

Author Details

Mitsuru Funakoshi
  • Department of Informatics, Kyushu University, Japan
Yuto Nakashima
  • Department of Informatics, Kyushu University, Japan
Shunsuke Inenaga
  • Department of Informatics, Kyushu University, Japan
Hideo Bannai
  • Department of Informatics, Kyushu University, Japan
Masayuki Takeda
  • Department of Informatics, Kyushu University, Japan

Funding

  • Nakashima, Yuto: Supported by JSPS KAKENHI Grant Number JP18K18002.
  • Inenaga, Shunsuke: Supported by JSPS KAKENHI Grant Number JP17H01697.
  • Bannai, Hideo: Supported by JSPS KAKENHI Grant Number JP16H02783.
  • Takeda, Masayuki: Supported by JSPS KAKENHI Grant Number JP18H04098.

Cite As Get BibTex

Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Faster Queries for Longest Substring Palindrome After Block Edit. In 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 128, pp. 27:1-27:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.CPM.2019.27

Abstract

Palindromes are important objects in strings which have been extensively studied from combinatorial, algorithmic, and bioinformatics points of views. Manacher [J. ACM 1975] proposed a seminal algorithm that computes the longest substring palindromes (LSPals) of a given string in O(n) time, where n is the length of the string. In this paper, we consider the problem of finding the LSPal after the string is edited. We present an algorithm that uses O(n) time and space for preprocessing, and answers the length of the LSPals in O(l + log log n) time, after a substring in T is replaced by a string of arbitrary length l. This outperforms the query algorithm proposed in our previous work [CPM 2018] that uses O(l + log n) time for each query.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorial algorithms
Keywords
  • palindromes
  • string algorithm
  • periodicity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Amihood Amir, Panagiotis Charalampopoulos, Costas S. Iliopoulos, Solon P. Pissis, and Jakub Radoszewski. Longest Common Factor After One Edit Operation. In SPIRE 2017, pages 14-26, 2017. Google Scholar
  2. Amihood Amir, Panagiotis Charalampopoulos, Solon P. Pissis, and Jakub Radoszewski. Longest Common Factor Made Fully Dynamic. CoRR, abs/1804.08731, 2018. URL: http://arxiv.org/abs/1804.08731.
  3. Alberto Apostolico, Dany Breslauer, and Zvi Galil. Parallel detection of all palindromes in a string. Theoretical Computer Science, 141:163-173, 1995. Google Scholar
  4. Michael A. Bender and Martin Farach-Colton. The LCA Problem Revisited. In LATIN 2000, pages 88-94, 2000. Google Scholar
  5. Michael A. Bender and Martin Farach-Colton. The Level Ancestor Problem simplified. Theor. Comput. Sci., 321(1):5-12, 2004. Google Scholar
  6. Petra Berenbrink, Funda Ergün, Frederik Mallmann-Trenn, and Erfan Sadeqi Azer. Palindrome Recognition In The Streaming Model. In STACS 2014, pages 149-161, 2014. Google Scholar
  7. O. Berkman and U. Vishkin. Finding level-ancestors in trees. J. Comput. System Sci., 48(2):214-230, 1994. Google Scholar
  8. Martin Farach-Colton, Paolo Ferragina, and S. Muthukrishnan. On the sorting-complexity of suffix tree construction. J. ACM, 47(6):987-1011, 2000. Google Scholar
  9. Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Longest substring palindrome after edit. In CPM 2018, pages 12:1-12:14, 2018. Google Scholar
  10. Pawel Gawrychowski, Tomohiro I, Shunsuke Inenaga, Dominik Köppl, and Florin Manea. Tighter Bounds and Optimal Algorithms for All Maximal α-gapped Repeats and Palindromes - Finding All Maximal α-gapped Repeats and Palindromes in Optimal Worst Case Time on Integer Alphabets. Theory Comput. Syst., 62(1):162-191, 2018. Google Scholar
  11. Pawel Gawrychowski, Oleg Merkurev, Arseny M. Shur, and Przemyslaw Uznanski. Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams. In CPM 2016, pages 18:1-18:13, 2016. Google Scholar
  12. Richard Groult, Élise Prieur, and Gwénaël Richomme. Counting distinct palindromes in a word in linear time. Inf. Process. Lett., 110(20):908-912, 2010. Google Scholar
  13. Dan Gusfield. Algorithms on Strings, Trees, and Sequences. Cambridge University Press, 1997. Google Scholar
  14. Roman Kolpakov and Gregory Kucherov. Searching for gapped palindromes. Theor. Comput. Sci., 410(51):5365-5373, 2009. Google Scholar
  15. Dmitry Kosolobov, Mikhail Rubinchik, and Arseny M. Shur. Finding Distinct Subpalindromes Online. In PSC 2013, pages 63-69, 2013. Google Scholar
  16. Glenn Manacher. A New Linear-Time "On-Line" Algorithm for Finding the Smallest Initial Palindrome of a String. Journal of the ACM, 22:346-351, 1975. Google Scholar
  17. U. Manber and G. Myers. Suffix arrays: A new method for on-line string searches. SIAM Journal on Computing, 22(5):935-948, 1993. Google Scholar
  18. W. Matsubara, S. Inenaga, A. Ishino, A. Shinohara, T. Nakamura, and K. Hashimoto. Efficient Algorithms to Compute Compressed Longest Common Substrings and Compressed Palindromes. Theor. Comput. Sci., 410(8-10):900-913, 2009. Google Scholar
  19. Alexandre H. L. Porto and Valmir C. Barbosa. Finding approximate palindromes in strings. Pattern Recognition, 35:2581-2591, 2002. Google Scholar
  20. Yuki Urabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Longest Lyndon Substring After Edit. In CPM 2018, pages 19:1-19:10, 2018. Google Scholar
  21. Peter Weiner. Linear Pattern Matching Algorithms. In 14th Annual Symposium on Switching and Automata Theory, pages 1-11, 1973. Google Scholar
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 About DROPS Imprint Privacy Contact