Fundamenta Informaticae - Volume 163, issue 3

Authors: Charalampopoulos, Panagiotis | Crochemore, Maxime | Pissis, Solon P.

Article Type: Other

DOI: 10.3233/FI-2018-1739

Citation: Fundamenta Informaticae, vol. 163, no. 3, pp. i-i, 2018

Authors: Grabowski, Szymon | Kociumaka, Tomasz | Radoszewski, Jakub

Article Type: Research Article

Abstract: We consider the Abelian longest common factor problem in two scenarios: when input strings are uncompressed and are of length at most n , and when the input strings are run-length encoded and their compressed representations have size at most m . The alphabet size is denoted by σ. For the uncompressed problem, we show an O (n 2 / log1+1/σ n )-time and 𝒪(n )-space algorithm in the case of σ = 𝒪(1), making a non-trivial use of tabulation. For the RLE-compressed problem, we show two algorithms: one working in 𝒪(m 2 σ2 log3 m ) time …and 𝒪(m (σ2 +log2 m )) space, which employs line sweep, and one that works in 𝒪(m 3 ) time and 𝒪(m ) space that applies in a careful way a sliding-window-based approach. The latter improves upon the previously known 𝒪(nm 2 )-time and 𝒪(m 4 )-time algorithms that were recently developed by Sugimoto et al. (IWOCA 2017) and Grabowski (SPIRE 2017), respectively. Show more

Keywords: Abelian longest common factor problem, jumbled pattern matching, run-length encoding (RLE)

DOI: 10.3233/FI-2018-1740

Citation: Fundamenta Informaticae, vol. 163, no. 3, pp. 225-244, 2018

Authors: Ganguly, Arnab | Patil, Manish | Shah, Rahul | Thankachan, Sharma V.

Article Type: Research Article

Abstract: Range LCP (longest common prefix) is an extension of the classical LCP problem and is defined as follows: Preprocess a string S [1...n ] of n characters, such that whenever an interval [i , j ] comes as a query, we can report max{|LCP(Sp , Sq )| | i ≤ p < q ≤ j } Here LCP(Sp , Sq ) is the longest common prefix of the suffixes of S starting at locations p and q , and |LCP(Sp , Sq )| is its length. This problem …was first addressed by Amir et al. [ISAAC, 2011]. They showed that the query can be answered in O (log log n ) time using an O (n log1+ɛ n ) space data structure for an arbitrarily small constant ɛ > 0. In an attempt to reduce the space bound, they presented a linear space data structure of O (d log log n ) query time, where d = (j − i + 1). In this paper, we present a new linear space data structure with an improved query time of O ( d log d ( log n ) 1 / 2 − ɛ ) . Show more

Keywords: String Algorithms, Suffix Trees, Range Query

DOI: 10.3233/FI-2018-1741

Citation: Fundamenta Informaticae, vol. 163, no. 3, pp. 245-251, 2018

Authors: Alzamel, Mai | Gao, Jia | Iliopoulos, Costas S. | Liu, Chang

Article Type: Research Article

Abstract: In this work, we consider a special type of uncertain sequence called weighted string. In a weighted string every position contains a subset of the alphabet and every letter of the alphabet is associated with a probability of occurrence such that the sum of probabilities at each position equals 1. Usually a cumulative weight threshold 1/z is specified, and one considers only strings that match the weighted string with probability at least 1/z . We provide an 𝒪(nz )-time and 𝒪(nz )-space off-line algorithm, where n is the length of the weighted string and 1/z …is the given threshold, to compute a smallest maximal palindromic factorization of a weighted string. This factorization has applications in hairpin structure prediction in a set of closely-related DNA or RNA sequences. Along the way, we provide an 𝒪(nz )-time and 𝒪(nz )-space off-line algorithm to compute maximal palindromes in weighted strings. Finally, we provide an experiment of our proposed algorithm. Show more

Keywords: weighted strings, palindromes, factorizations

DOI: 10.3233/FI-2018-1742

Citation: Fundamenta Informaticae, vol. 163, no. 3, pp. 253-266, 2018

Authors: Hooshmand, Sahar | Tavakoli, Neda | Abedin, Paniz | Thankachan, Sharma V.

Article Type: Research Article

Abstract: The Average Common Substring (ACS) is a popular alignment-free distance measure for phylogeny reconstruction. The ACS of a sequence X[1, x ] w.r.t. another sequence Y[1, y ] is ACS(X,   Y)   =   1 x ∑ i = 1 x max j lcp ( X [ i ,   x ] ,   Y [ j ,   y ] ) The lcp(·, ·) of two input sequences is the length of their longest common prefix. The ACS can be computed in O (n …) space and time, where n = x + y is the input size. The compressed string matching is the study of string matching problems with the following twist: the input data is in a compressed format and the underling task must be performed with little or no decompression. In this paper, we revisit the ACS problem under this paradigm where the input sequences are given in their run-length encoded format. We present an algorithm to compute ACS(X, Y) in O (N logN ) time using O (N ) space, where N is the total length of sequences after run-length encoding. Show more

Keywords: String Algorithms, Suffix Trees, RL Encoding, Compression

DOI: 10.3233/FI-2018-1743

Citation: Fundamenta Informaticae, vol. 163, no. 3, pp. 267-273, 2018

Authors: Mhaskar, Neerja | Smyth, W. F.

Article Type: Research Article

Abstract: We study a central problem of string processing: the compact representation of a string by its frequently-occurring substrings. In this paper we propose an effective, easily-computed form of quasi-periodicity in strings, the frequency cover ; that is, the longest of those repeating substrings u of w , |u | > 1, that occurs the maximum number of times in w . The advantage of this generalization is that it is not only applicable to all strings but also that it is the only generalized notion of cover yet proposed, which can be computed efficiently in …linear time and space. We describe a simple data structure called the repeating substring frequency array (ℛ𝒮ℱ array) for the string w , which we show can be constructed in 𝒪 (n ) time and 𝒪 (n ) space, where |w | = n . We then use ℛ𝒮ℱ to compute all the frequency covers of w in linear time and space. Our research also allows us to give an alternate algorithm to compute all non-extendible repeating substrings in w , also in 𝒪 (n ) time and space. Show more

Keywords: quasi-periodicities, covers, non-extendible repeating substring

DOI: 10.3233/FI-2018-1744

Citation: Fundamenta Informaticae, vol. 163, no. 3, pp. 275-289, 2018

Authors: Chairungsee, Supaporn

Article Type: Research Article

Abstract: In this article, we introduce new methods to compute the Longest Previous nonoverlapping Factor (LPnF) table. The LPnF table is the table that stores the maximal length of factors re-occurring at each position of a string without overlapping and this table is related to Ziv-Lempel factorization of a text which is useful for text compression and data compression. The LPnF table has the important role for data compression, string algorithms and computational biology. In this paper, we present three approaches to produce the LPnF table of a string from its augmented position heap, from its position heap, and from its …suffix heap. We also present the experimental results from these three solutions. The algorithms run in linear time with linear memory space. Show more

Keywords: Longest Previous non-overlapping Factor, Augmented position heap, Position heap, Suffix heap, Data compression, Text compression

DOI: 10.3233/FI-2018-1745

Citation: Fundamenta Informaticae, vol. 163, no. 3, pp. 291-304, 2018