115 Search Results for "Inenaga, Shunsuke"

Volume

LIPIcs, Volume 296

35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024)

CPM 2024, June 25-27, 2024, Fukuoka, Japan

Editors: Shunsuke Inenaga and Simon J. Puglisi

Document
DOI: 10.4230/LIPIcs.SEA.2026.16
Efficient Large-Scale Text Precompression via Approximate LZ77 Parsings

Authors: Patrick Dinklage

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract
The LZ77 [Lempel and Ziv, 1977] compression scheme is ubiquitous: it lies at the core of everyday general-purpose standard compressors such as gzip or zstd, but also behind the scenes of many applications such as the compression of payloads transmitted in networks. Computing the exact LZ77 parsing is largely solved in theory: it can be done in sublinear time and space, in compressed space and in external memory, to name but some scenarios. However, these approaches are often impractical for everyday use due to their intensive time or space requirements. Standard compressors tackle this issue by introducing heuristics that go hand in hand with sophisticated encoding schemes to achieve very good compression fast and in small space, however, they only have a local view (e.g., a sliding window) on the input, potentially missing out on long-range repetitions that may be located far apart from one another. In this work, we design and implement - in C++ and leveraging shared-memory parallelism - compression pipelines that first precompress the input using an approximate LZ77 parsing taking care of long-range repetitions. This then serves as an assist to standard compressors for producing a succinct encoding of the remaining short and local repetitions. Similar approaches have been considered by [Kosolobov et al., 2020] and [Nalbach, 2024], respectively using Relative Lempel Ziv [Kuruppu et al. 2010] or the string synchronizing set [Kempa & Kociumaka, 2019]. We fill a gap taking the route via the prefix-free parsing [Boucher et al., 2019], using an intermediate result of [Hong et al., 2023]. On large repetitive inputs of tens of gigabytes, our pipelines are orders of magnitudes faster than the state of the art for computing the exact LZ77 parsing, use space less than the input size and still - despite producing more phrases - achieve the best overall compression in comparison to related work.
Cite as

Patrick Dinklage. Efficient Large-Scale Text Precompression via Approximate LZ77 Parsings. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 16:1-16:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dinklage:LIPIcs.SEA.2026.16,
  author =	{Dinklage, Patrick},
  title =	{{Efficient Large-Scale Text Precompression via Approximate LZ77 Parsings}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{16:1--16:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.16},
  URN =		{urn:nbn:de:0030-drops-260204},
  doi =		{10.4230/LIPIcs.SEA.2026.16},
  annote =	{Keywords: compression, algorithm engineering, parallel computation}
}
Document
DOI: 10.4230/LIPIcs.CPM.2026.34
LZBE: An LZ-Style Compressor Supporting O(log n)-Time Random Access

Authors: Hiroki Shibata, Yuto Nakashima, Yutaro Yamaguchi, and Shunsuke Inenaga

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

Abstract
An LZ-like factorization of a string divides it into factors, each being either a single character or a copy of a preceding substring. While grammar-based compression schemes support efficient random access with space linear in the compressed size, no comparable guarantees are known for general LZ-like factorizations. This limitation motivated restricted variants such as LZ-End [Kreft and Navarro, 2013] and height-bounded LZ (LZHB) [Bannai et al., 2024], which trade off some compression efficiency for faster access. In this paper, we introduce LZ-Begin-End (LZBE), a new LZ-like variant in which every copy factor must refer to a contiguous sequence of preceding factors. This structural restriction ensures that any context-free grammar can be transformed into an LZBE factorization of the same size. We further study the greedy LZBE factorization, which selects each copy factor to be as long as possible while processing the input from left to right, and show that it can be computed in linear time. Moreover, we exhibit a family of strings for which the greedy LZBE factorization is asymptotically smaller than the smallest grammar. These results demonstrate that the LZBE scheme is strictly more expressive than grammar-based compression in the worst case. To support fast queries, we propose a data structure for LZBE-compressed strings that permits O(log n)-time random access within space linear in the compressed size, where n is the length of the input string.
Cite as

Hiroki Shibata, Yuto Nakashima, Yutaro Yamaguchi, and Shunsuke Inenaga. LZBE: An LZ-Style Compressor Supporting O(log n)-Time Random Access. In 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 369, pp. 34:1-34:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{shibata_et_al:LIPIcs.CPM.2026.34,
  author =	{Shibata, Hiroki and Nakashima, Yuto and Yamaguchi, Yutaro and Inenaga, Shunsuke},
  title =	{{LZBE: An LZ-Style Compressor Supporting O(log n)-Time Random Access}},
  booktitle =	{37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)},
  pages =	{34:1--34: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.34},
  URN =		{urn:nbn:de:0030-drops-259609},
  doi =		{10.4230/LIPIcs.CPM.2026.34},
  annote =	{Keywords: data compression, Lempel-Ziv parsing, string algorithms, random access}
}
Document
DOI: 10.4230/LIPIcs.CPM.2026.35
Efficient Index for Square Pattern Matching

Authors: Po-Chun Chen, Che-Wei Tsao, Wing-Kai Hon, and Dominik Köppl

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

Abstract
A string S is called a square if it can be written as the concatenation of two identical strings. Two strings P and Q of the same length are said to square match if, for every substring of P, it is a square if and only if the corresponding substring of Q is also a square. The square pattern matching problem asks for locating all substrings of a given text T of length n that square match a query pattern P of length m. This notion captures similarity in repetition structures and is motivated by applications in areas such as bioinformatics and music structure analysis. In this paper, we introduce a novel technique, called the longest prefix square (LPS) encoding, which represents the square structure of a string as an integer array of the same length. We show that two strings square match if and only if they have identical LPS encodings. Based on this result, we construct an index solving the square pattern matching problem in time O(m lg m + occ) using O(nlg²n) bits of space, where occ denotes the number of occurrences of substrings in T that square match P. If the LPS encoding of P is precomputed, the query time improves to O(m + occ).
Cite as

Po-Chun Chen, Che-Wei Tsao, Wing-Kai Hon, and Dominik Köppl. Efficient Index for Square Pattern Matching. In 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 369, pp. 35:1-35:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.CPM.2026.35,
  author =	{Chen, Po-Chun and Tsao, Che-Wei and Hon, Wing-Kai and K\"{o}ppl, Dominik},
  title =	{{Efficient Index for Square Pattern Matching}},
  booktitle =	{37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)},
  pages =	{35:1--35: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.35},
  URN =		{urn:nbn:de:0030-drops-259617},
  doi =		{10.4230/LIPIcs.CPM.2026.35},
  annote =	{Keywords: string algorithms, pattern matching, indexing, squares}
}
Document
DOI: 10.4230/LIPIcs.CPM.2026.2
Near-Real-Time Solutions for Online String Problems

Authors: Dominik Köppl and Gregory Kucherov

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

Abstract
Based on the Breslauer-Italiano online suffix tree construction algorithm (2013) with double logarithmic worst-case guarantees on the update time per letter, we develop near-real-time algorithms for several classical problems on strings, including the computation of the longest repeating suffix array, the (reversed) Lempel-Ziv 77 factorization, and the maintenance of minimal unique substrings, all in an online manner. Our solutions improve over the best known running times for these problems in terms of the worst-case time per letter, for which we achieve a poly-log-logarithmic time complexity, within a linear space. Best known results for these problems require a poly-logarithmic time complexity per letter or only provide amortized complexity bounds. As a result of independent interest, we give conversions between the longest previous factor array and the longest repeating suffix array in space and time bounds based on their irreducible representations, which can have sizes sublinear in the length of the input string.
Cite as

Dominik Köppl and Gregory Kucherov. Near-Real-Time Solutions for Online String Problems. In 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 369, pp. 2:1-2:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{koppl_et_al:LIPIcs.CPM.2026.2,
  author =	{K\"{o}ppl, Dominik and Kucherov, Gregory},
  title =	{{Near-Real-Time Solutions for Online String Problems}},
  booktitle =	{37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)},
  pages =	{2:1--2:17},
  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.2},
  URN =		{urn:nbn:de:0030-drops-259287},
  doi =		{10.4230/LIPIcs.CPM.2026.2},
  annote =	{Keywords: online algorithms, string algorithms, suffix tree, real-time computation, Lempel-Ziv factorization, minimal unique substrings}
}
Document
DOI: 10.4230/LIPIcs.CPM.2026.3
Computing k-mers in Graphs

Authors: Jarno N. Alanko and Máximo Pérez-López

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

Abstract
We initiate the study of computational problems on k-mers (strings of length k) in labeled graphs. As a starting point, we consider the problem of counting the number of distinct k-mers found on the walks of a graph. We establish that this is #P-hard, even on connected deterministic DAGs. However, in the class of deterministic Wheeler graphs (Gagie, Manzini, and Sirén, TCS 2017), we show that distinct k-mers of such a graph W = (V, E) can be counted using O(|W|k) or O(n⁴ log k) arithmetic operations, where n = |V|, m = |E| and |W| = n+m. The latter result uses a new generalization of the technique of prefix doubling to Wheeler graphs. To generalize our results beyond Wheeler graphs, we discuss ways to transform a graph into a Wheeler graph in a manner that preserves the k-mers. As an application of our k-mer counting algorithms, we construct a representation of the de Bruijn graph of the k-mers that occupies O(n_k + |W|k log(max_{1 ≤ 𝓁 ≤ k} n_𝓁) + σlog m) bits of space, where n_𝓁 is the number of distinct 𝓁-mers in the Wheeler graph, and σ is the size of the alphabet. We show how to construct it in the same time complexity. Given that the Wheeler graph can be exponentially smaller than the de Bruijn graph, for large k this provides a theoretical improvement over previous de Bruijn graph construction methods from graphs, which must spend Ω(k) time per k-mer in the graph.
Cite as

Jarno N. Alanko and Máximo Pérez-López. Computing k-mers in Graphs. In 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 369, pp. 3:1-3:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{alanko_et_al:LIPIcs.CPM.2026.3,
  author =	{Alanko, Jarno N. and P\'{e}rez-L\'{o}pez, M\'{a}ximo},
  title =	{{Computing k-mers in Graphs}},
  booktitle =	{37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)},
  pages =	{3:1--3:17},
  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.3},
  URN =		{urn:nbn:de:0030-drops-259294},
  doi =		{10.4230/LIPIcs.CPM.2026.3},
  annote =	{Keywords: Wheeler graph, Wheeler language, de Bruijn graph, graph, k-mer, q-gram, DFA, #P-hard}
}
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.5
Efficient Grammar Compression via RLZ-Based RePair

Authors: Rahul Varki, Travis Gagie, and Christina Boucher

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

Abstract
Among grammar-based compression techniques, RePair is a notable offline encoding scheme known for its simplicity and powerful combinatorial properties, producing compact grammars by repeatedly replacing the most frequent adjacent pairs of symbols, known as bigrams. However, RePair’s memory usage scales poorly with input size, as it loads the entire text into memory. In contrast, Relative Lempel-Ziv (RLZ) parsing offers a scalable and lightweight online encoding scheme that losslessly represents a text in terms of phrases that refer to a reference string, but it often fails to expose deeper structural patterns. We introduce an algorithm that produces a RePair grammar from the RLZ parse of the input, leveraging the strengths of both methods. Our method, RLZ-RePair, performs bigram replacements systematically, preserving the integrity of the RLZ phrases throughout the RePair iterations. When the reference is well chosen, our method achieves the same grammar as standard RePair while significantly reducing both memory usage and the number of bigram replacements. In particular, we show that RLZ-RePair can reduce memory usage by more than 80% while incurring only a modest runtime increase compared to RePair. To our knowledge, RLZ-RePair is one of the first scalable methods that constructs exact RePair grammars, resulting in a grammar-based compressor that is both practical for large datasets and faithful to the theoretical elegance of RePair.
Cite as

Rahul Varki, Travis Gagie, and Christina Boucher. Efficient Grammar Compression via RLZ-Based RePair. In 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 369, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{varki_et_al:LIPIcs.CPM.2026.5,
  author =	{Varki, Rahul and Gagie, Travis and Boucher, Christina},
  title =	{{Efficient Grammar Compression via RLZ-Based RePair}},
  booktitle =	{37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)},
  pages =	{5:1--5:15},
  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.5},
  URN =		{urn:nbn:de:0030-drops-259310},
  doi =		{10.4230/LIPIcs.CPM.2026.5},
  annote =	{Keywords: RePair, RLZ, Grammar Compression}
}
Document
DOI: 10.4230/LIPIcs.CPM.2026.6
Improved Bounds on the Maximum Number of Distinct Squares in Circular Words

Authors: Panagiotis Charalampopoulos, Manal Mohamed, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń, and Wiktor Zuba

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

Abstract
We investigate the asymptotic growth of function CS(n), which maps n to the maximum number of distinct squares in a circular word of length n (that is, the maximum number of distinct squares of length at most n in a word ww of length 2n). We improve upon the lower bound of 1.25n established by Amit and Gawrychowski [SPIRE 2017] and the straightforward upper bound of 2n, which follows from the recent result of Brlek and Li [Comb. Theory, 2025] stating that there are fewer than n squares in standard (i.e., non-circular) words of length n. (Previously, Amit and Gawrychowski gave an upper bound of 32/15n using a weaker upper bound on squares in standard words.) Specifically, we show that CS(n) ≤ ⌈1.8 n⌉ and that, for infinitely many n, CS(n) ≥ 1.5n-𝒪(√n). For the lower bound, we exploit the combinatorial structure of Fibonacci words to construct a family of square-rich circular words. For the upper bound, we exploit density properties of the starting positions of long squares, adapting an approach of Amit and Gawrychowski.
Cite as

Panagiotis Charalampopoulos, Manal Mohamed, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń, and Wiktor Zuba. Improved Bounds on the Maximum Number of Distinct Squares in Circular Words. In 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 369, pp. 6:1-6:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{charalampopoulos_et_al:LIPIcs.CPM.2026.6,
  author =	{Charalampopoulos, Panagiotis and Mohamed, Manal and Radoszewski, Jakub and Rytter, Wojciech and Wale\'{n}, Tomasz and Zuba, Wiktor},
  title =	{{Improved Bounds on the Maximum Number of Distinct Squares in Circular Words}},
  booktitle =	{37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)},
  pages =	{6:1--6: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.6},
  URN =		{urn:nbn:de:0030-drops-259325},
  doi =		{10.4230/LIPIcs.CPM.2026.6},
  annote =	{Keywords: circular words, squares, repetitions}
}
Document
DOI: 10.4230/LIPIcs.CPM.2026.10
R-Enum Revisited: Speedup and Extension for Context-Sensitive Repeats and Net Frequencies

Authors: Kotaro Kimura and Tomohiro I

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

Abstract
A repeat is a substring that occurs at least twice in a string, and is called a maximal repeat if it cannot be extended outwards without reducing its frequency. Nishimoto and Tabei [CPM, 2021] proposed r-enum, an algorithm to enumerate various characteristic substrings, including maximal repeats, in a string T of length n in O(r) words of compressed working space, where r ≤ n is the number of runs in the Burrows-Wheeler transform (BWT) of T. Given the run-length encoded BWT (RLBWT) of T, r-enum runs in O(n log log_w (n/r)) time in addition to the time linear to the number of output strings, where w = Θ(log n) is the word size. In this paper, we first improve the O(n log log_w (n/r)) term to O(n). We next extend r-enum to compute other context-sensitive repeats such as near-supermaximal repeats (NSMRs) and supermaximal repeats, as well as the context diversity for every maximal repeat in the same complexities. Furthermore, we study net occurrences: An occurrence of a repeat is called a net occurrence if it is not covered by another repeat, and the net frequency of a repeat is the number of its net occurrences. With this terminology, an NSMR is a repeat with a positive net frequency. Given the RLBWT of T, we show how to compute the set 𝒮^{nsmr} of all NSMRs in T together with their net frequency/occurrences in O(n) time and O(r) space. We also show that an O(r)-space data structure can be built from the RLBWT to compute the net frequency/occurrences of any pattern in optimal time. The data structure is built in O(r) space and in O(n) time with high probability or deterministic O(n + |𝒮^{nsmr}| log log min(σ, |𝒮^{nsmr}|)) time, where σ ≤ r is the alphabet size of T. To achieve this, we prove that the total number of net occurrences is less than 2r. With the duality between net occurrences and minimal unique substrings (MUSs), we get a new upper bound 2r of the number of MUSs in T, which may be of independent interest.
Cite as

Kotaro Kimura and Tomohiro I. R-Enum Revisited: Speedup and Extension for Context-Sensitive Repeats and Net Frequencies. In 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 369, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kimura_et_al:LIPIcs.CPM.2026.10,
  author =	{Kimura, Kotaro and I, Tomohiro},
  title =	{{R-Enum Revisited: Speedup and Extension for Context-Sensitive Repeats and Net Frequencies}},
  booktitle =	{37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)},
  pages =	{10:1--10:14},
  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.10},
  URN =		{urn:nbn:de:0030-drops-259361},
  doi =		{10.4230/LIPIcs.CPM.2026.10},
  annote =	{Keywords: Supermaximal repeats, Largest maximal repeats, Net frequencies, Run-length Burrows-Wheeler transform, Compressed data mining}
}
Document
DOI: 10.4230/LIPIcs.CPM.2026.13
Totally Unclustered BWT Images of Any Length over Non-Binary Alphabets

Authors: Gabriele Fici, Estéban Gabory, Giuseppe Romana, and Marinella Sciortino

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

Abstract
We prove that for every integer n > 0 and for every alphabet Σ_k of size k ≥ 3, there exist words of length n whose Burrows-Wheeler Transform (BWT) is totally unclustered, i.e., it consists of exactly n runs with no two consecutive equal symbols. These words represent the worst-case behavior of the clustering effect of the BWT. We also establish a lower bound on their number. This contrasts with the binary case, where the existence of infinitely many totally unclustered BWT images is still an open problem, related to Artin’s conjecture on primitive roots.
Cite as

Gabriele Fici, Estéban Gabory, Giuseppe Romana, and Marinella Sciortino. Totally Unclustered BWT Images of Any Length over Non-Binary Alphabets. In 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 369, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fici_et_al:LIPIcs.CPM.2026.13,
  author =	{Fici, Gabriele and Gabory, Est\'{e}ban and Romana, Giuseppe and Sciortino, Marinella},
  title =	{{Totally Unclustered BWT Images of Any Length over Non-Binary Alphabets}},
  booktitle =	{37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)},
  pages =	{13:1--13:17},
  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.13},
  URN =		{urn:nbn:de:0030-drops-259399},
  doi =		{10.4230/LIPIcs.CPM.2026.13},
  annote =	{Keywords: Burrows-Wheeler Transform, BWT-runs, Repetitiveness Measure, Clustering Effect, Generalized de Bruijn Words}
}
Document
DOI: 10.4230/LIPIcs.CPM.2026.8
Constant Multiplicative Sensitivity on the CDAWGs

Authors: Rikuya Hamai, Hiroto Fujimaru, and Shunsuke Inenaga

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

Abstract
Compact directed acyclic word graphs (CDAWGs) [Blumer et al. 1987] are a fundamental data structure on strings with applications in text pattern searching, data compression, and pattern discovery. Intuitively, the CDAWG of a string T is obtained by merging isomorphic subtrees of the suffix tree [Weiner 1973] of the same string T, and thus CDAWGs are a compact indexing structure. Indeed, the CDAWG size 𝖾 can be sublinear in n for some highly repetitive strings. Of its various applications, the CDAWG allows for computing pattern occurrences, maximal exact matches (MEMs), minimal absent words (MAWs), and minimal unique substrings (MUSs) in optimal time using O(𝖾) space. For designing space-efficient data storage, it is crucial that the underlying data structure is robust against data edits and errors. As a mathematical measure for this, the notion of compression sensitivity [Akagi et al. 2023] was introduced as the maximum of the size increase in the compressed data structures after edits operations. In this paper, we investigate the sensitivity of CDAWGs when a single character edit operation is performed at an arbitrary position in the input string T. We show that the size of the CDAWG after an edit operation on T is asymptotically at most 8 times larger than the original CDAWG before the edit. This O(1) upper bound significantly improves on the only known upper bound O(n/log n) for the problem.
Cite as

Rikuya Hamai, Hiroto Fujimaru, and Shunsuke Inenaga. Constant Multiplicative Sensitivity on the CDAWGs. In 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 369, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hamai_et_al:LIPIcs.CPM.2026.8,
  author =	{Hamai, Rikuya and Fujimaru, Hiroto and Inenaga, Shunsuke},
  title =	{{Constant Multiplicative Sensitivity on the CDAWGs}},
  booktitle =	{37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)},
  pages =	{8:1--8:17},
  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.8},
  URN =		{urn:nbn:de:0030-drops-259345},
  doi =		{10.4230/LIPIcs.CPM.2026.8},
  annote =	{Keywords: string data structures, maximal repeats, data compression, compression sensitivity, CDAWGs}
}
Document
DOI: 10.4230/LIPIcs.CPM.2026.14
Hardness Results on Characteristics for Elastic-Degenerate Strings

Authors: Dominik Köppl and Jannik Olbrich

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

Abstract
Generalizations of plain strings have been proposed as a compact way to represent a collection of nearly identical sequences or to express uncertainty at specific text positions by enumerating all possibilities. While a plain string stores a character at each of its positions, generalizations consider a set of characters (indeterminate strings), a set of strings of equal length (generalized degenerate strings, or shortly GD strings), or a set of strings of arbitrary lengths (elastic-degenerate strings, or shortly ED strings). These generalizations are of importance to compactly represent such type of data, and find applications in bioinformatics for representing and maintaining a set of genetic sequences of the same taxonomy or a multiple sequence alignment. To be of use, attention has been drawn to answering various query types such as pattern matching or measuring similarity of ED strings by generalizing techniques known to plain strings. However, for some types of queries, it has been shown that a generalization of a polynomial-time solvable query on classic strings becomes NP-hard on ED strings, e.g. [Russo et al., 2022]. In that light, we wonder about other types of queries that are of particular interest to bioinformatics: unique substrings, absent words, anti-powers, longest previous factors, and Lempel-Ziv-like compression schemes. While we obtain a polynomial time algorithm for a variation of longest previous factors, we show that all other problems are NP-hard to compute, some of them even under the restriction that the input can be modeled as an indeterminate or GD string.
Cite as

Dominik Köppl and Jannik Olbrich. Hardness Results on Characteristics for Elastic-Degenerate Strings. In 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 369, pp. 14:1-14:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{koppl_et_al:LIPIcs.CPM.2026.14,
  author =	{K\"{o}ppl, Dominik and Olbrich, Jannik},
  title =	{{Hardness Results on Characteristics for Elastic-Degenerate Strings}},
  booktitle =	{37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)},
  pages =	{14:1--14:25},
  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.14},
  URN =		{urn:nbn:de:0030-drops-259409},
  doi =		{10.4230/LIPIcs.CPM.2026.14},
  annote =	{Keywords: Elastic-degenerate strings, NP-hardness, longest common factor, minimal unique substring, minimal absent word, anti-power, longest previous factor}
}
Document
DOI: 10.4230/LIPIcs.CPM.2026.17
Sensitivity of Repetitiveness Measures to String Reversal

Authors: Hideo Bannai, Yuto Fujie, Peaker Guo, Shunsuke Inenaga, Yuto Nakashima, Simon J. Puglisi, and Cristian Urbina

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

Abstract
We study the impact that string reversal can have on several repetitiveness measures. First, we exhibit an infinite family of strings where the number, r, of runs in the run-length encoding of the Burrows-Wheeler transform (BWT) can increase additively by Θ(n) when reversing the string. This substantially improves the known Ω(log n) lower-bound for the additive sensitivity of r and it is asymptotically tight. We generalize our result to other variants of the BWT, including the variant with an appended end-of-string symbol and the bijective BWT. We show that an analogous result holds for the size z of the Lempel-Ziv 77 (LZ) parsing of the text, and also for some of its variants, including the non-overlapping LZ parsing, and the LZ-end parsing. Moreover, we describe a family of strings for which the ratio z(w^R)/z(w) approaches 3 from below as |w| → ∞. We also show an asymptotically tight lower-bound of Θ(n) for the additive sensitivity of the size v of the smallest lexicographic parsing to string reversal. Finally, we show that the multiplicative sensitivity of v to reversing the string is Θ(log n), and this lower-bound is also tight. Overall, our results expose the limitations of repetitiveness measures that are widely used in practice, against string reversal - a simple and natural data transformation.
Cite as

Hideo Bannai, Yuto Fujie, Peaker Guo, Shunsuke Inenaga, Yuto Nakashima, Simon J. Puglisi, and Cristian Urbina. Sensitivity of Repetitiveness Measures to String Reversal. In 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 369, pp. 17:1-17:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bannai_et_al:LIPIcs.CPM.2026.17,
  author =	{Bannai, Hideo and Fujie, Yuto and Guo, Peaker and Inenaga, Shunsuke and Nakashima, Yuto and Puglisi, Simon J. and Urbina, Cristian},
  title =	{{Sensitivity of Repetitiveness Measures to String Reversal}},
  booktitle =	{37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)},
  pages =	{17:1--17: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.17},
  URN =		{urn:nbn:de:0030-drops-259434},
  doi =		{10.4230/LIPIcs.CPM.2026.17},
  annote =	{Keywords: String reversal, Repetitiveness measures, Burrows-Wheeler transform, Lempel-Ziv parsing, Lexicographic parsings}
}
Document
DOI: 10.4230/LIPIcs.CPM.2026.21
A Bitwise Approach to SCER Matching in Indeterminate Strings

Authors: Simone Faro, Dominik Köppl, Thierry Lecroq, and Francesco Pio Marino

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

Abstract
We study the problem of matching a determinate pattern against an indeterminate text of the same length n, where each text position is a set of possible characters drawn from an alphabet Σ of size σ. We study this matching problem under the order-preserving and parameterized matching setting. For that, we encode character sets by bit expressions using sum-free sequences. This encoding enables constant-time character comparisons and avoids explicit set operations. We present an optimal 𝒪(n) time algorithm for order-preserving matching and an 𝒪(n+(σ_p^x ⋅ σ_p^y) √{σ_p^x + σ_p^y}) time algorithm for parameterized matching, where σ_p^x and σ_p^y denote the number of distinct parameterized symbols in the pattern and the text, respectively. The proposed techniques significantly reduce overhead while maintaining exactness, offering practical performance improvements for pattern matching under uncertainty. Additionally, we extend the parameterized matching framework to allow mismatches, for which we present an algorithm with time complexity 𝒪(σ² n log n + n σ² √σ log(n σ)).
Cite as

Simone Faro, Dominik Köppl, Thierry Lecroq, and Francesco Pio Marino. A Bitwise Approach to SCER Matching in Indeterminate Strings. In 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 369, pp. 21:1-21:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{faro_et_al:LIPIcs.CPM.2026.21,
  author =	{Faro, Simone and K\"{o}ppl, Dominik and Lecroq, Thierry and Marino, Francesco Pio},
  title =	{{A Bitwise Approach to SCER Matching in Indeterminate Strings}},
  booktitle =	{37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)},
  pages =	{21:1--21:17},
  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.21},
  URN =		{urn:nbn:de:0030-drops-259470},
  doi =		{10.4230/LIPIcs.CPM.2026.21},
  annote =	{Keywords: string matching, indeterminate strings, SCER matching}
}
  • Refine by Type
  • 114 Document/PDF
  • 52 Document/HTML
  • 1 Volume

  • Refine by Publication Year
  • 22 2026
  • 30 2025
  • 32 2024
  • 4 2022
  • 3 2020
  • Show More...

  • Refine by Author
  • 39 Inenaga, Shunsuke
  • 30 Bannai, Hideo
  • 21 Takeda, Masayuki
  • 17 Nakashima, Yuto
  • 11 Köppl, Dominik
  • Show More...

  • Refine by Series/Journal
  • 107 LIPIcs
  • 6 OASIcs
  • 1 DagSemProc

  • Refine by Classification
  • 40 Theory of computation → Pattern matching
  • 18 Mathematics of computing → Combinatorics on words
  • 14 Mathematics of computing → Combinatorial algorithms
  • 14 Theory of computation → Data compression
  • 11 Theory of computation → Data structures design and analysis
  • Show More...

  • Refine by Keyword
  • 10 string algorithms
  • 8 suffix trees
  • 7 Fibonacci words
  • 7 pattern matching
  • 6 Burrows-Wheeler Transform
  • 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