检索结果-内蒙古大学图书馆

Data Structures for Computing Unique Palindromes in Static and Non-Static strings

ALGORITHMICA 2024年第3期86卷 852-873页

作者： Mieno, Takuya Funakoshi, Mitsuru Univ Electrocommun Dept Comp & Network Engn 1-5-1 Chofugaoka Chofu 1828585 Japan Kyushu Univ Dept Informat 744 Motooka Nishi Ku Fukuoka 8190395 Japan Japan Soc Promot Sci 5-3-1 KojimachiChiyoda Ku Tokyo 1020083 Japan

A palindromic substring T [i.. j] of a string T is said to be a shortest unique palindromic substring (SUPS) in T for an interval [ p, q] if T [i.. j] is a shortest palindromic substring such that T [i.. j] occurs only once in T, and [i, j] contains [p, q]. The SUPS problem is, given a string T of length n, 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 O(alpha) time after O(n)-time preprocessing, where a is the number of SUPSs to output (Inoue in J Discrete algorithms 52-53:122-132, 2018). In this paper, we first show that a is at most 4, and the upper bound is tight. We also show that the total sum of lengths of minimal unique palindromic substrings of string T, which is strongly related to SUPSs, is O(n). Then, we present the first O(n)-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 O(log logW) time and update data structures in amortized O(log s + log logW) time, where W is the size of the window, and s 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 O(n) time for preprocessing and answers any k SUPS queries in O(log n log log n + k log log n) 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.

关键词： string algorithms Palindromes Shortest unique palindromic substrings Range minimum queries Dynamic data structures Compact data structures

来源：评论

学校读者我要写书评

暂无评论

Closest periodic vectors in L_p spaces

引用

THEORETICAL COMPUTER SCIENCE 2014年 533卷 26-36页

作者： Amir, Amihood Eisenberg, Estrella Levy, Avivit Lewenstein, Noa Bar Ilan Univ Dept Comp Sci IL-52900 Ramat Gan Israel Johns Hopkins Univ Dept Comp Sci Baltimore MD 21218 USA Shenkar Coll Dept Software Engn Ramat Gan Israel Univ Haifa CRI IL-31905 Haifa Israel Netanya Coll Netanya Israel

The problem of finding the period of a vector V is central to many applications. Let V' be a periodic vector closest to V under some metric. We seek this V', or more precisely we seek the smallest period that generates V'. In this paper we consider the problem of finding the closest periodic vector in L-p spaces. The measures of "closeness" that we consider are the metrics in the different L-p spaces. Specifically, we consider the L-1, L-2 and L-infinity metrics. In particular, for a given n-dimensional vector V, we develop O(n(2)) time algorithms (a different algorithm for each metric) that construct the smallest period that defines such a periodic n-dimensional vector V'. We call that vector the closest periodic vector of V under the appropriate metric. We also show (three) (O) over tilde (n) time constant approximation algorithms for the period of the approximate closest periodic vector. (C) 2014 Elsevier B.V. All rights reserved.

关键词： string algorithms Approximate periodicity Closest vector

来源：评论

学校读者我要写书评

暂无评论

A formal framework for stringology

引用

DISCRETE APPLIED MATHEMATICS 2020年 274卷 141-151页

作者： Soltys, Michael Mhaskar, Neerja Calif State Univ Channel Isl Dept Comp Sci One Univ Dr Camarillo CA 93012 USA McMaster Univ Dept Comp & Software 1280 Main St West Hamilton ON L8S 4K1 Canada

A new formal framework for stringology is proposed, which consists of a three-sorted logical theory S designed to capture the combinatorial reasoning about finite strings. We propose a language L-8 for expressing assertions about strings, and study in detail two sets of formulas Sigma(B)(0), a set of formulas decidable in polytime, and Sigma(B)(1), a set of formulas with the property that those provable in S yield polytime algorithms. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Proof complexity string algorithms

来源：评论

学校读者我要写书评

暂无评论

Motif matching using gapped patterns

引用

THEORETICAL COMPUTER SCIENCE 2014年第C期548卷 1-13页

作者： Giaquinta, Emanuele Fredriksson, Kimmo Grabowski, Szymon Tomescu, Alexandru I. Ukkonen, Esko Univ Helsinki Dept Comp Sci FIN-00014 Helsinki Finland Lodz Univ Technol Inst Appl Comp Sci PL-90924 Lodz Poland Univ Eastern Finland Sch Comp FI-70211 Kuopio Finland Helsinki Inst Informat Technol Helsinki Finland

We present new algorithms for the problem of multiple string matching of gapped patterns, where a gapped pattern is a sequence of strings such that there is a gap of fixed length between each two consecutive strings. The problem has applications in the discovery of transcription factor binding sites in DNA sequences when using generalized versions of the Position Weight Matrix model to describe transcription factor specificities. In these models a motif can be matched as a set of gapped patterns with unit-length keywords. The existing algorithms for matching a set of gapped patterns are worst-case efficient but not practical, or vice versa, in this particular case. The novel algorithms that we present are based on dynamic programming and bit-parallelism, and lie in a middle-ground among the existing algorithms. In fact, their time complexity is close to the best existing bound and, yet, they are also practical. We also provide experimental results which show that the presented algorithms are fast in practice, and preferable if all the strings in the patterns have unit-length. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Combinatorial problems string algorithms Multiple pattern matching Pattern matching with gaps Word-level parallelism

来源：评论

学校读者我要写书评

暂无评论

Computing longest palindromic substring after single-character or block-wise edits

引用

THEORETICAL COMPUTER SCIENCE 2021年 859卷 116-133页

作者： Funakoshi, Mitsuru Nakashima, Yuto Inenaga, Shunsuke Bannai, Hideo Takeda, Masayuki Kyushu Univ Dept Informat Fukuoka Japan Japan Sci & Technol Agcy PRESTO Saitama Japan Tokyo Med & Dent Univ M&D Data Sci Ctr Tokyo Japan

Palindromes are important objects in strings which have been extensively studied from combinatorial, algorithmic, and bioinformatics points of views. It is known that the length of the longest palindromic substrings (LPSs) of a given string T of length n can be computed in O (n) time by Manacher's algorithm [12]. In this paper, we consider the problem of finding the LPS after the string is edited. We present an algorithm that uses O (n) time and space for preprocessing, and answers the length of the LPSs in O(log(min{sigma, log n})) time after a 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 LPSs in O (l + log log n) time, after an existing substring in T is replaced by a string of arbitrary length l. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Palindromes string algorithms Periodicity

来源：评论

学校读者我要写书评

暂无评论

Optimal parallel analysis and decomposition of partially occluded strings

引用

PARALLEL COMPUTING 2000年第4期26卷 483-494页

作者： Iliopoulos, CS Reid, JF Kings Coll London Dept Comp Sci Algorithm Design Grp London WC2R 2LS England Curtin Univ Technol Sch Comp Bentley WA 6102 Australia Univ Padua Dipartimento Elettron & Informat I-35131 Padua Italy

This is a theoretical study of partially occluded one-dimensional images. Here, we consider ''valid" images composed from a given set of objects, where some objects appearing in the image may be partially obstructed by others. A CRCW PRAM algorithm is presented here for validating a one-dimensional image x of length n over a set of k objects of equal length in O(log logn) time with linear work, where k is a fixed integer. (C) 2000 Published by Elsevier Science B.V. All rights reserved.

关键词： string algorithms PRAM algorithms pattern recognition

来源：评论

学校读者我要写书评

暂无评论

Sequential and parallel algorithms for all-pair k-mismatch maximal common substrings

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2020年 144卷 68-79页

作者： Chockalingam, Sriram P. Thankachan, Sharma, V Aluru, Srinivas Georgia Inst Technol Inst Data Engn & Sci 756 W Peachtree St NW12th Floor Atlanta GA 30308 USA Georgia Inst Technol Dept Computat Sci & Engn 756 W Peachtree St NW13th Floor Atlanta GA 30308 USA Univ Cent Florida Dept Comp Sci Orlando FL 32816 USA

Identifying long pairwise maximal common substrings among a large set of sequences is a frequently used construct in computational biology, with applications in DNA sequence clustering and assembly. Due to errors made by sequencers, algorithms that can accommodate a small number of differences are of particular interest. Formally, let D be a collection of n sequences of total length N, phi be a length threshold, and k be a mismatch threshold. The goal is to identify and report all k-mismatch maximal common substrings of length at least phi over all pairs of strings in D. Heuristics based on seed-and-extend style filtering techniques are often employed in such applications. However, such methods cannot provide any provably efficient run time guarantees. To this end, we present a sequential algorithm with an expected run time of O(N log(k) N+occ), where occ is the output size. We then present a distributed memory parallel algorithm with an expected run time of O ((N/P log N + occ) log(k) N) using O (log(k+1) N) expected rounds of global communications, under some realistic assumptions, where p is the number of processors. Finally, we demonstrate the performance and scalability of our algorithms using experiments on large high throughput sequencing data. (C) 2020 Elsevier Inc. All rights reserved.

关键词： Approximate sequence matching string algorithms Suffix trees Hamming distance Parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Fast algorithms for the Shortest Unique Palindromic Substring Problem on Run-Length Encoded strings

引用

THEORY OF COMPUTING SYSTEMS 2020年第7期64卷 1273-1291页

作者： Watanabe, Kiichi Nakashima, Yuto Inenaga, Shunsuke Bannai, Hideo Takeda, Masayuki Kyushu Univ Dept Informat Fukuoka Japan Japan Sci & Technol Agcy PRESTO Saitama Japan

For a string S, a palindromic substring S[i..j] is said to be a shortest unique palindromic substring (SUPS) for an interval [s, t] in S, if S[i..j] occurs exactly once in S, the interval [i, j] contains [s, t], and every palindromic substring containing [s, t] which is shorter than S[i.. j] occurs at least twice in S. In this paper, we study the problem of answering SUPS queries on run-length encoded strings. We show how to preprocess a given run-length encoded string RLES of size m in O(m) space and O(m log sigma(RLES) + m root log m/log log m) time so that all SUPSs for any subsequent query interval can be answered in O(root log m/log log m + alpha) time, where a is the number of outputs, and sigma(RLES) is the number of distinct runs of RLES. Additionaly, we consider a variant of the SUPS problem where a query interval is also given in a run-length encoded form. For this variant of the problem, we present two alternative algorithms with faster queries. The first one answers queries in O(root log log m/log log log m + alpha) time and can be built in O(mlog sigma(RLES) + m root log m/log log m) time, and the second one answers queries in O(log log m + alpha) time and can be built in O(m log sigma(RLES)) time. Both of these data structures require O(m) space.

关键词： string algorithms Run length encoding Palindromes Shortest unique substrings

来源：评论

学校读者我要写书评

暂无评论

Linearized Suffix Tree: an Efficient Index Data Structure with the Capabilities of Suffix Trees and Suffix Arrays

引用

ALGORITHMICA 2008年第3期52卷 350-377页

作者： Kim, Dong Kyue Kim, Minhwan Park, Heejin Hanyang Univ Coll Informat & Commun Seoul 133791 South Korea Pusan Natl Univ Div Comp Engn Pusan 609735 South Korea Hanyang Univ Div Elect & Comp Engn Seoul 133791 South Korea

Suffix trees and suffix arrays are fundamental full-text index data structures to solve problems occurring in string processing. Since suffix trees and suffix arrays have different capabilities, some problems are solved more efficiently using suffix trees and others are solved more efficiently using suffix arrays. We consider efficient index data structures with the capabilities of both suffix trees and suffix arrays without requiring much space. When the size of an alphabet is small, enhanced suffix arrays are such index data structures. However, when the size of an alphabet is large, enhanced suffix arrays lose the power of suffix trees. Pattern searching in an enhanced suffix array takes O(m vertical bar Sigma vertical bar) time while pattern searching in a suffix tree takes O(m log vertical bar Sigma vertical bar) time where m is the length of a pattern and Sigma is an alphabet. In this paper, we present linearized suffix trees which are efficient index data structures with the capabilities of both suffix trees and suffix arrays even when the size of an alphabet is large. A linearized suffix tree has all the functionalities of the enhanced suffix array and supports the pattern search in O(m log vertical bar Sigma vertical bar) time. In a different point of view, it can be considered a practical implementation of the suffix tree supporting O(m log vertical bar Sigma vertical bar)-time pattern search. In addition, we also present two efficient algorithms for computing suffix links on the enhanced suffix array and the linearized suffix tree. These are the first algorithms that run in O(n) time without using the range minima query. Our experimental results show that our algorithms are faster than the previous algorithms.

关键词： Suffix trees Suffix arrays Index data structures string algorithms

来源：评论

学校读者我要写书评

暂无评论

Text sparsification via local maxima

引用

THEORETICAL COMPUTER SCIENCE 2003年第1-3期304卷 341-364页

作者： Crescenzi, P Del Lungo, A Grossi, R Lodi, E Pagli, L Rossi, G Univ Siena Dipartimento Matemat I-53100 Siena Italy Univ Florence Dipartimento Sistemi & Informat I-50134 Florence Italy Univ Pisa Dipartimento Informat I-56125 Pisa Italy Univ Roma Tor Vergata Dipartimento Matemat I-00133 Rome Italy

in this paper we investigate some properties and algorithms related to a text sparsification technique based on the identification of local maxima in the given string. As the number of local maxima depends on the order assigned to the alphabet symbols, we first consider the case in which the order can be chosen in an arbitrary way. We show that looking for an order that minimizes the number of local maxima in the given text string is an NP-hard problem. Then, we consider the case in which the order is fixed a priori. Even though the order is not necessarily optimal, we can exploit the property that the average number of local maxima induced by the order in an arbitrary text is approximately one third of the text length. In particular, we describe how to iterate the process of selecting the local maxima by one or more iterations, so as to obtain a sparsified text. We show how to use this technique to filter the access to unstructured texts, which appear to have no natural division in words. Finally, we experimentally show that our approach can be successfully used in order to create a space efficient index for searching sufficiently long patterns in a DNA sequence as quickly as a full index. (C) 2003 Elsevier B.V. All rights reserved.

关键词： computational complexity NP-completeness pattern matching string algorithms text indexing data structures

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：