236 research outputs found
Computing Palindromes on a Trie in Linear Time
No full textA trie is a rooted tree such that each edge is labeled by a single character from the alphabet, and the labels of out-going edges from the same node are mutually distinct. Given a trie with n edges, we show how to compute all distinct palindromes and all maximal palindromes on in O(n) time, in the case of integer alphabets of size polynomial in n. This improves the state-of-the-art O(n log h)-time algorithms by Funakoshi et al. [PSC 2019], where h is the height of . Using our new algorithms, the eertree with suffix links for a given trie can readily be obtained in O(n) time. Further, our trie-based O(n)-space data structure allows us to report all distinct palindromes and maximal palindromes in a query string represented in the trie , in output optimal time. This is an improvement over an existing (naïve) solution that precomputes and stores all distinct palindromes and maximal palindromes for each and every string in the trie separately, using a total O(n²) preprocessing time and space, and reports them in output optimal time upon query
Non-Rectangular Convolutions and (Sub-)Cadences with Three Elements
No full textThe discrete acyclic convolution computes the 2n+1 sums ∑_{i+j=k|(i,j)∈[0,1,2,… ,n]²} a_i b_j in ?(n log n) time. By using suitable offsets and setting some of the variables to zero, this method provides a tool to calculate all non-zero sums ∑_{i+j=k|(i,j)∈ P∩ℤ²} a_i b_j in a rectangle P with perimeter p in ?(p log p) time.
This paper extends this geometric interpretation in order to allow arbitrary convex polygons P with k vertices and perimeter p. Also, this extended algorithm only needs ?(k + p(log p)² log k) time.
Additionally, this paper presents fast algorithms for counting sub-cadences and cadences with 3 elements using this extended method
Edit and Alphabet-Ordering Sensitivity of Lex-Parse
No full textWe investigate the compression sensitivity [Akagi et al., 2023] of lex-parse [Navarro et al., 2021] for two operations: (1) single character edit and (2) modification of the alphabet ordering, and give tight upper and lower bounds for both operations (i.e., we show Θ(log n) bounds for strings of length n). For both lower bounds, we use the family of Fibonacci words. For the bounds on edit operations, our analysis makes heavy use of properties of the Lyndon factorization of Fibonacci words to characterize the structure of lex-parse
Longest substring palindrome after edit
No full textIt is known that the length of the longest substring palindromes (LSPals) of a given string T of length n can be computed in O(n) time by Manacher's algorithm [J. ACM '75]. In this paper, we consider the problem of finding the LSPal after the string is edited. We present an algorithm that uses O(n) time and space for preprocessing, and answers the length of the LSPals in O(log (min {sigma, log n })) time after single character substitution, insertion, or deletion, where sigma denotes the number of distinct characters appearing in T. We also propose an algorithm that uses O(n) time and space for preprocessing, and answers the length of the LSPals in O(l + log n) time, after an existing substring in T is replaced by a string of arbitrary length l
Faster Queries for Longest Substring Palindrome After Block Edit
No full textPalindromes are important objects in strings which have been extensively studied from combinatorial, algorithmic, and bioinformatics points of views. Manacher [J. ACM 1975] proposed a seminal algorithm that computes the longest substring palindromes (LSPals) of a given string in O(n) time, where n is the length of the string. In this paper, we consider the problem of finding the LSPal after the string is edited. We present an algorithm that uses O(n) time and space for preprocessing, and answers the length of the LSPals in O(l + log log n) time, after a substring in T is replaced by a string of arbitrary length l. This outperforms the query algorithm proposed in our previous work [CPM 2018] that uses O(l + log n) time for each query
Optimal LZ-End Parsing Is Hard
No full textLZ-End is a variant of the well-known Lempel-Ziv parsing family such that each phrase of the parsing has a previous occurrence, with the additional constraint that the previous occurrence must end at the end of a previous phrase. LZ-End was initially proposed as a greedy parsing, where each phrase is determined greedily from left to right, as the longest factor that satisfies the above constraint [Kreft & Navarro, 2010]. In this work, we consider an optimal LZ-End parsing that has the minimum number of phrases in such parsings. We show that a decision version of computing the optimal LZ-End parsing is NP-complete by showing a reduction from the vertex cover problem. Moreover, we give a MAX-SAT formulation for the optimal LZ-End parsing adapting an approach for computing various NP-hard repetitiveness measures recently presented by [Bannai et al., 2022]. We also consider the approximation ratio of the size of greedy LZ-End parsing to the size of the optimal LZ-End parsing, and give a lower bound of the ratio which asymptotically approaches 2
Detecting k-(Sub-)Cadences and Equidistant Subsequence Occurrences
No full textThe equidistant subsequence pattern matching problem is considered. Given a pattern string P and a text string T, we say that P is an equidistant subsequence of T if P is a subsequence of the text such that consecutive symbols of P in the occurrence are equally spaced. We can consider the problem of equidistant subsequences as generalizations of (sub-)cadences. We give bit-parallel algorithms that yield o(n²) time algorithms for finding k-(sub-)cadences and equidistant subsequences. Furthermore, O(nlog² n) and O(nlog n) time algorithms, respectively for equidistant and Abelian equidistant matching for the case |P| = 3, are shown. The algorithms make use of a technique that was recently introduced which can efficiently compute convolutions with linear constraints
Height-Bounded Lempel-Ziv Encodings
No full textWe introduce height-bounded LZ encodings (LZHB), a new family of compressed representations that are variants of Lempel-Ziv parsings with a focus on bounding the worst-case access time to arbitrary positions in the text directly via the compressed representation. An LZ-like encoding is a partitioning of the string into phrases of length 1 which can be encoded literally, or phrases of length at least 2 which have a previous occurrence in the string and can be encoded by its position and length. An LZ-like encoding induces an implicit referencing forest on the set of positions of the string. An LZHB encoding is an LZ-like encoding where the height of the implicit referencing forest is bounded. An LZHB encoding with height constraint h allows access to an arbitrary position of the underlying text using O(h) predecessor queries. While computing the optimal (i.e., smallest) LZHB encoding efficiently seems to be difficult [Cicalese & Ugazio 2024, arXiv, to appear at DLT 2024], we give the first linear time algorithm for strings over a constant size alphabet that computes the greedy LZHB encoding, i.e., the string is processed from beginning to end, and the longest prefix of the remaining string that can satisfy the height constraint is taken as the next phrase. Our algorithms significantly improve both theoretically and practically, the very recently and independently proposed algorithms by Lipták et al. (CPM 2024). We also analyze the size of height bounded LZ encodings in the context of repetitiveness measures, and show that there exists a constant c such that the size ẑHB(c log n) of the optimal LZHB encoding whose height is bounded by c log n for any string of length n is O(ĝrl), where ĝrl is the size of the smallest run-length grammar. Furthermore, we show that there exists a family of strings such that ẑHB(c log n) = o(ĝrl), thus making ẑHB(c log n) one of the smallest known repetitiveness measures for which O(polylogn) time access is possible using linear (O(ẑHB(c log n))) space.Peer reviewe
Data structures for computing unique palindromes in static and non-static strings
No full textA palindromic substring of a string is said to be a shortest
unique palindromic substring (SUPS) in for an interval if is a shortest palindromic substring such that occurs only once
in , and contains . The SUPS problem is, given a string
of length , to construct a data structure that can compute all the SUPSs for
any given query interval. It is known that any SUPS query can be answered in
time after -time preprocessing, where is the number
of SUPSs to output [Inoue et al., 2018]. In this paper, we first show that
is at most , and the upper bound is tight. We also show that the
total sum of lengths of minimal unique palindromic substrings of string ,
which is strongly related to SUPSs, is . Then, we present the first
-bits data structures that can answer any SUPS query in constant time.
Also, we present an algorithm to solve the SUPS problem for a sliding window
that can answer any query in time and update data structures in
amortized time, where is the size of the
window, and is the alphabet size. Furthermore, we consider the SUPS
problem in the after-edit model and present an efficient algorithm. Namely, we
present an algorithm that uses time for preprocessing and answers any
SUPS queries in time after single
character substitution. Finally, as a by-product, we propose a fully-dynamic
data structure for range minimum queries (RmQs) with a constraint where the
width of each query range is limited to poly-logarithmic. The constrained RmQ
data structure can answer such a query in constant time and support a
single-element edit operation in amortized constant time
The undecidability of deriving atomic formulas from Horn formulas
No full textTechnical report DCS-TR-5
- …
