conference

Computing Longest Common Substring and All Palindromes from Compressed Strings.

Wataru Matsubara, Shunsuke Inenaga, Akira Ishino, Ayumi Shinohara, Tomoyuki Nakamura, Kazuo Hashimoto

SOFSEM 2008: Theory and Practice of Computer Science, 34th Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 19-25, 2008, Proceedings, , pp.364-375 (2008), [peer-reviewed]
Event Date: January 19-25, 2008

DOI External Link

Abstract / 概要

This paper studies two problems on compressed strings described in terms of straight line programs (SLPs). One is to compute the length of the longest common substring of two given SLP-compressed strings, and the other is to compute all palindromes of a given…

DOI: 10.1007/978-3-540-77566-9_31