59 Search Results for "I, Tomohiro"

Document
DOI: 10.4230/LIPIcs.SEA.2026.4
Integer Programming Models for the Median of a 0-1 String Set Under Levenshtein Distance

Authors: Claudio Arbib, Andrea D'Ascenzo, Oya E. Karaşan, and Andrea Pizzuti

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

Abstract
The Median String Problem calls for finding a string that minimizes the average distance from a given set of strings. Under the Levenshtein (or edit) metric, the problem is NP-hard even for binary strings. We devised two novel integer linear programming models for this case and tested them against the only formulation we are aware of in the literature. Our numerical experiments attest to the efficacy of the proposed approach.
Cite as

Claudio Arbib, Andrea D'Ascenzo, Oya E. Karaşan, and Andrea Pizzuti. Integer Programming Models for the Median of a 0-1 String Set Under Levenshtein Distance. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{arbib_et_al:LIPIcs.SEA.2026.4,
  author =	{Arbib, Claudio and D'Ascenzo, Andrea and Kara\c{s}an, Oya E. and Pizzuti, Andrea},
  title =	{{Integer Programming Models for the Median of a 0-1 String Set Under Levenshtein Distance}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{4:1--4:15},
  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.4},
  URN =		{urn:nbn:de:0030-drops-260081},
  doi =		{10.4230/LIPIcs.SEA.2026.4},
  annote =	{Keywords: Levenshtein Distance, Median String Problem, Integer Programming}
}
Document
DOI: 10.4230/LIPIcs.SEA.2026.9
Bounding the Average Move Structure Query for Faster and Smaller RLBWT Permutations

Authors: Nathaniel K. Brown and Ben Langmead

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

Abstract
The move structure represents permutations with long contiguously permuted intervals in compressed space with optimal query time. They have become an important feature of compressed text indexes using space proportional to the number of Burrows-Wheeler Transform (BWT) runs, often applied in genomics. This is in thanks not only to theoretical improvements over past approaches, but great cache efficiency and average case query time in practice. This is true even without using the worst case guarantees provided by the interval splitting balancing of the original result. In this paper, we show that an even simpler type of splitting, length capping by truncating long intervals, bounds the average move structure query time to optimal whilst obtaining a superior construction time than the traditional approach. This also proves constant query time when amortized over a full traversal of a single cycle permutation from an arbitrary starting position. Such a scheme has surprising benefits both in theory and practice. For a move structure with r runs over a domain n, we replace all O(r log n)-bit components to reduce the overall representation by O(r log r)-bits. The worst case query time is also improved to O(log n/r) without balancing. An O(r)-time and space construction lets us apply the method to run-length encoded BWT (RLBWT) permutations such as LF and ϕ to obtain optimal-time algorithms for BWT inversion and suffix array (SA) enumeration in O(r) working space. Finally, we introduce the Orbit library, providing flexible plug and play move structure support, and use it to evaluate our splitting approach. Experiments find length capping construction is faster and uses less memory than balancing, and results in faster move structure queries: up to ∼ 17 times faster when compared to an unbalanced representation of ϕ. We also see a space reduction in practice, with at least a ∼ 40% disk size decrease for LF across large repetitive genomic collections when compared to a balanced/unbalanced move structure.
Cite as

Nathaniel K. Brown and Ben Langmead. Bounding the Average Move Structure Query for Faster and Smaller RLBWT Permutations. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 9:1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{brown_et_al:LIPIcs.SEA.2026.9,
  author =	{Brown, Nathaniel K. and Langmead, Ben},
  title =	{{Bounding the Average Move Structure Query for Faster and Smaller RLBWT Permutations}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{9:1--9:15},
  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.9},
  URN =		{urn:nbn:de:0030-drops-260136},
  doi =		{10.4230/LIPIcs.SEA.2026.9},
  annote =	{Keywords: Move Structure, Burrows-Wheeler Transform, Permutation}
}
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.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.SWAT.2026.39
Faster Approximate Linear Matroid Intersection

Authors: Tatsuya Terao

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
We consider a fast approximation algorithm for the linear matroid intersection problem. In this problem, we are given two r × n matrices M₁ and M₂, and the objective is to find a largest set of columns that are linearly independent in both M₁ and M₂. We design a (1 - ε)-approximation algorithm with time complexity Õ_{ε}(nnz(M₁) + nnz(M₂) + r_{*}^{ω}), where nnz(M_i) denotes the number of nonzero entries in M_i for i = 1, 2, r_{*} denotes the maximum size of a common independent set, and ω < 2.372 denotes the matrix multiplication exponent. Our approximation algorithm is faster than the exact algorithm by Harvey [FOCS'06 & SICOMP'09] and Cheung-Kwok-Lau [STOC'12 & JACM'13], which runs in Õ(nnz(M₁) + nnz(M₂) + n r_{*}^{ω - 1}) time. We also develop a fast (1 - ε)-approximation algorithm for the weighted version of the linear matroid intersection problem. In fact, we design a (1 - ε)-approximation algorithm for weighted linear matroid intersection with time complexity Õ_{ε}(nnz(M₁) + nnz(M₂) + r_{*}^{ω}). Our algorithm improves upon the (1 - ε)-approximation algorithm by Huang-Kakimura-Kamiyama [SODA'16 & Math. Program.'19], which runs in Õ_{ε}(nnz(M₁) + nnz(M₂) + nr_{*}^{ω - 1}) time. To obtain these results, we combine Quanrud’s adaptive sparsification framework [ICALP'24] with a simple yet effective method for efficiently checking whether a given vector lies in the linear span of a subset of vectors, which is of independent interest.
Cite as

Tatsuya Terao. Faster Approximate Linear Matroid Intersection. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 39:1-39:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{terao:LIPIcs.SWAT.2026.39,
  author =	{Terao, Tatsuya},
  title =	{{Faster Approximate Linear Matroid Intersection}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{39:1--39:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.39},
  URN =		{urn:nbn:de:0030-drops-260756},
  doi =		{10.4230/LIPIcs.SWAT.2026.39},
  annote =	{Keywords: Linear matroid intersection, fast approximation algorithm}
}
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.16
Merging RLBWTs Adaptively

Authors: Travis Gagie

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

Abstract
We show how to merge two run-length compressed Burrows-Wheeler Transforms (RLBWTs) into a run-length compressed extended Burrows-Wheeler Transform (eBWT) in O (r) space and O ((r + L) log (m + n)) time, where m and n are the lengths of the uncompressed strings, r is the number of runs in the final eBWT and L is the sum of its irreducible LCP values.
Cite as

Travis Gagie. Merging RLBWTs Adaptively. In 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 369, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gagie:LIPIcs.CPM.2026.16,
  author =	{Gagie, Travis},
  title =	{{Merging RLBWTs Adaptively}},
  booktitle =	{37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)},
  pages =	{16:1--16: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.16},
  URN =		{urn:nbn:de:0030-drops-259420},
  doi =		{10.4230/LIPIcs.CPM.2026.16},
  annote =	{Keywords: Burrows-Wheeler Transform, run-length compression, RLBWT, construction, merging}
}
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
  • 59 Document/PDF
  • 46 Document/HTML

  • Refine by Publication Year
  • 19 2026
  • 27 2025
  • 1 2024
  • 2 2023
  • 3 2018
  • Show More...

  • Refine by Author
  • 15 I, Tomohiro
  • 11 Bannai, Hideo
  • 9 Inenaga, Shunsuke
  • 8 Köppl, Dominik
  • 6 Nakashima, Yuto
  • Show More...

  • Refine by Series/Journal
  • 55 LIPIcs
  • 4 OASIcs

  • Refine by Classification
  • 16 Theory of computation → Pattern matching
  • 12 Theory of computation → Data compression
  • 8 Mathematics of computing → Combinatorics on words
  • 6 Theory of computation → Parameterized complexity and exact algorithms
  • 4 Theory of computation → Data structures design and analysis
  • Show More...

  • Refine by Keyword
  • 7 Burrows-Wheeler Transform
  • 4 pattern matching
  • 4 string algorithms
  • 3 Fibonacci words
  • 3 Grammar compression
  • 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