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

Absent Subsequences in Words

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Kosche, Maria Koß, Tore Manea, Florin Siemer, Stefan Institute for Computer Science Georg-August University Göttingen Germany

An absent factor of a string w is a string u which does not occur as a contiguous sub-string (a.k.a. factor) inside w. We extend this well-studied notion and define absent subsequences: a string u is an absent subsequence of a string w if u does not occur as subsequence (a.k.a. scattered factor) inside w. Of particular interest to us are minimal absent subsequences, i.e., absent subsequences whose every subsequence is not absent, and shortest absent subsequences, i.e., absent subsequences of minimal length. We show a series of combinatorial and algorithmic results regarding these two notions. For instance: we give combinatorial characterisations of the sets of minimal and, respectively, shortest absent subsequences in a word, as well as compact representations of these sets;we show how we can test efficiently if a string is a shortest or minimal absent subsequence in a word, and we give efficient algorithms computing the lexicographically smallest absent subsequence of each kind;also, we show how a data structure for answering shortest absent subsequence-queries for the factors of a given string can be efficiently computed. © 2021, CC BY.

关键词： string searching algorithms

Near-Optimal Quantum Algorithm for Finding the Longest Common Substring between Run-Length Encoded strings

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Lee, Tzu-Ching Lin, Han-Hsuan National Tsing Hua University Taiwan

We give a near-optimal quantum algorithm for the longest common substring (LCS) problem between two run-length encoded (RLE) strings, with the assumption that the prefix-sums of the run-lengths are given. Our algorithm costs (Equation presented) time, while the query lower bound for the problem is Ω˜(n2/3/d1/6), where n and ñ are the encoded and decoded length of the inputs, respectively, and d is the encoded length of the LCS. We justify the use of prefix-sum oracles for two reasons. First, we note that creating the prefix-sum oracle only incurs a constant overhead in the RLE compression. Second, we show that, without the oracles, there is a Ω(n/log2 n) lower bound on the quantum query complexity of finding the LCS given two RLE strings due to a reduction of PARITY to the problem. With a small modification, our algorithm also solves the longest repeated substring problem for an RLE string. © 2024, CC BY.

关键词： string searching algorithms

Greedy-reduction from Shortest Linear Superstring to Shortest Circular Superstring

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Cazaux, Bastien Rivals, Eric LIRMM University of Montpellier CNRS Montpellier France

A superstring of a set of strings correspond to a string which contains all the other strings as substrings. The problem of finding the Shortest Linear Superstring is a well-know and well-studied problem in stringology. We present here a variant of this problem, the Shortest Circular Superstring problem where the sought superstring is a circular string. We show a strong link between these two problems and prove that the Shortest Circular Superstring problem is NP-complete. Moreover, we propose a new conjecture on the approximation ratio of the Shortest Circular Superstring *** Codes 68W32 Copyright © 2020, The Authors. All rights reserved.

关键词： string searching algorithms

Faster batched range minimum queries

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Grabowski, Szymon Kowalski, Tomasz Lodz University of Technology Institute of Applied Computer Science Al. Politechniki 11 Lodz90-924 Poland

Range Minimum Query (RMQ) is an important building brick of many compressed data structures and string matching algorithms. Although this problem is essentially solved in theory, with sophisticated data structures allowing for constant time queries, there are scenarios in which the number of queries, q, is rather small and given beforehand, which encourages to use a simpler approach. A recent work by Alzamel et al. starts with contracting the input array to a much shorter one, with its size proportional to q. In this work, we build upon their solution, speeding up handling small batches of queries by a factor of 3.8-7.8 (the gap grows with q). The key idea that helped us achieve this advantage is adapting the wellknown Sparse Table technique to work on blocks, with speculative block minima comparisons. We also propose an even much faster (but possibly using more space) variant without the array *** Codes 68W32 Copyright © 2017, The Authors. All rights reserved.

关键词： string searching algorithms

Fast cartesian tree matching

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Song, Siwoo Ryu, Cheol Faro, Simone Lecroq, Thierry Park, Kunsoo Seoul National University Seoul Korea Republic of University of Catania Catania Italy Normandie University Rouen France

Cartesian tree matching is the problem of finding all substrings of a given text which have the same Cartesian trees as that of a given pattern. So far there is one linear-time solution for Cartesian tree matching, which is based on the KMP algorithm. We improve the running time of the previous solution by introducing new representations. We present the framework of a binary filtration method and an efficient verification technique for Cartesian tree matching. Any exact string matching algorithm can be used as a filtration for Cartesian tree matching on our framework. We also present a SIMD solution for Cartesian tree matching suitable for short patterns. By experiments we show that known string matching algorithms combined on our framework of binary filtration and efficient verification produce algorithms of good performances for Cartesian tree matching. Copyright © 2019, The Authors. All rights reserved.

关键词： string searching algorithms