3 Search Results for "Matsubara, Wataru"

Document
DOI: 10.4230/LIPIcs.CPM.2026.4
Compact Representation of Maximal Palindromes

Authors: Takuya Mieno

Published in: LIPIcs, Volume 369, 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)

Abstract
Palindromes are strings that read the same forward and backward. The computation of palindromic structures within strings is a fundamental problem in string algorithms, being motivated by potential applications in formal language theory and bioinformatics. Although the number of palindromic factors in a string of length n can be quadratic, they can be implicitly represented in O(n log n) bits of space by storing the lengths of all maximal palindromes in an integer array, which can be computed in O(n) time [Manacher, 1975]. In this paper, we propose a novel O(n)-bit representation of all maximal palindromes in a string, which enables O(1)-time retrieval of the length of the maximal palindrome centered at any given position. The data structure can be constructed in O(n) time from the input string of length n. Since Manacher’s algorithm and the notion of maximal palindromes are widely utilized for solving numerous problems involving palindromic structures, our compact representation will accelerate the development of more space-efficient solutions to such problems. Indeed, as the first application of our compact representation of maximal palindromes, we present a data structure of size O(n) bits that can compute the longest palindrome appearing in any given factor of a string of length n in O(log n) time.
Cite as

Takuya Mieno. Compact Representation of Maximal Palindromes. In 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 369, pp. 4:1-4:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{mieno:LIPIcs.CPM.2026.4,
  author =	{Mieno, Takuya},
  title =	{{Compact Representation of Maximal Palindromes}},
  booktitle =	{37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)},
  pages =	{4:1--4:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-420-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{369},
  editor =	{Bille, Philip and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2026.4},
  URN =		{urn:nbn:de:0030-drops-259304},
  doi =		{10.4230/LIPIcs.CPM.2026.4},
  annote =	{Keywords: palindromes, succinct data structures, internal queries}
}
Document
DOI: 10.4230/LIPIcs.CPM.2026.23
Improved Bounds on the Sum of Exponents of Runs in a String

Authors: Arkadiusz Czarkowski

Published in: LIPIcs, Volume 369, 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)

Abstract
A substring of a word is a run if it is at least twice as long as its minimum period and cannot be extended to either side with the same period. The exponent of a run is the quotient of its length and its minimum period. ρ(n) is the maximum number of runs in a string of length n, while σ(n) is the maximum sum of exponents of runs in a string of length n. While quite tight bounds on ρ(n) are known (0.944575712n ≤ ρ(n) ≤ n), the best upper bound on σ(n) is 3n whereas the best lower bound on σ(n) is 2.035n. In this paper, we improve the upper bound on σ(n) to 2.3n and the lower bound on σ(n) to 2.04448n. We also provide an improved upper bound on σ(n) of 2.2n in the case of a binary alphabet. Our results are achieved using a combination of theoretical and computer-based approaches.
Cite as

Arkadiusz Czarkowski. Improved Bounds on the Sum of Exponents of Runs in a String. In 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 369, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{czarkowski:LIPIcs.CPM.2026.23,
  author =	{Czarkowski, Arkadiusz},
  title =	{{Improved Bounds on the Sum of Exponents of Runs in a String}},
  booktitle =	{37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)},
  pages =	{23:1--23:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-420-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{369},
  editor =	{Bille, Philip and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2026.23},
  URN =		{urn:nbn:de:0030-drops-259494},
  doi =		{10.4230/LIPIcs.CPM.2026.23},
  annote =	{Keywords: strings, runs, sum of exponents of runs, Lyndon words, L-roots, maximal repetitions, combinatorics on words}
}
Document
DOI: 10.4230/DagSemProc.08261.5
An Efficient Algorithm to Test Square-Freeness of Strings Compressed by Balanced Straight Line Program

Authors: Wataru Matsubara, Shunsuke Inenaga, and Ayumi Shinohara

Published in: Dagstuhl Seminar Proceedings, Volume 8261, Structure-Based Compression of Complex Massive Data (2008)

Abstract
In this paper we study the problem of deciding whether a given compressed string contains a square. A string x is called a square if x = zz and z = u^k implies k = 1 and u = z. A string w is said to be square-free if no substrings of w are squares. Many efficient algorithms to test if a given string is square-free, have been developed so far. However, very little is known for testing square-freeness of a given compressed string. In this paper, we give an O(max(n^2; n log^2 N))-time O(n^2)-space solution to test square-freeness of a given compressed string, where n and N are the size of a given compressed string and the corresponding decompressed string, respectively. Our input strings are compressed by balanced straight line program (BSLP). We remark that BSLP has exponential compression, that is, N = O(2^n). Hence no decompress-then-test approaches can be better than our method in the worst case.
Cite as

Wataru Matsubara, Shunsuke Inenaga, and Ayumi Shinohara. An Efficient Algorithm to Test Square-Freeness of Strings Compressed by Balanced Straight Line Program. In Structure-Based Compression of Complex Massive Data. Dagstuhl Seminar Proceedings, Volume 8261, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{matsubara_et_al:DagSemProc.08261.5,
  author =	{Matsubara, Wataru and Inenaga, Shunsuke and Shinohara, Ayumi},
  title =	{{An Efficient Algorithm to Test Square-Freeness of Strings Compressed by Balanced Straight Line Program}},
  booktitle =	{Structure-Based Compression of Complex Massive Data},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8261},
  editor =	{Stefan B\"{o}ttcher and Markus Lohrey and Sebastian Maneth and Wojcieh Rytter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08261.5},
  URN =		{urn:nbn:de:0030-drops-16804},
  doi =		{10.4230/DagSemProc.08261.5},
  annote =	{Keywords: Square Freeness, Straight Line Program}
}
  • Refine by Type
  • 3 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 2 2026
  • 1 2008

  • Refine by Author
  • 1 Czarkowski, Arkadiusz
  • 1 Inenaga, Shunsuke
  • 1 Matsubara, Wataru
  • 1 Mieno, Takuya
  • 1 Shinohara, Ayumi

  • Refine by Series/Journal
  • 2 LIPIcs
  • 1 DagSemProc

  • Refine by Classification
  • 1 Mathematics of computing → Combinatorial algorithms
  • 1 Mathematics of computing → Combinatorics on words
  • 1 Theory of computation → Pattern matching

  • Refine by Keyword
  • 1 L-roots
  • 1 Lyndon words
  • 1 Square Freeness
  • 1 Straight Line Program
  • 1 combinatorics on words
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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