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

INFORMATION AND COMPUTATION 2003年第1期181卷 57-74页

作者： Amir, A Cole, R Hariharan, R Lewenstein, M Porat, E IBM Corp Thomas J Watson Res Ctr Yorktown Hts NY 10598 USA Bar Ilan Univ Dept Comp Sci IL-52900 Ramat Gan Israel Georgia Tech Coll Comp Atlanta GA 30332 USA NYU Courant Inst Math Sci Dept Comp Sci New York NY 10012 USA Indian Inst Sci CSA Dept Bangalore 560012 Karnataka India

We propose a new paradigm for string matching, namely structural matching. In structural matching, the text and pattern contents are not important. Rather, some areas in the text and pattern, such as intervals, are singled out. A "match" is a text location where a specified relation between the text and pattern areas is satisfied. In particular we define the structural matching problem of overlap (parity) matching. We seek the text locations where all overlaps of the given pattern and text intervals have even length. We show that this problem can be solved in time O(n log m), where the text length is n and the pattern length is m. As an application of overlap matching, we show how to reduce the string matching with swaps problem to the overlap matching problem. The string matching with swaps problem is the problem of string matching in the presence of local swaps. The best deterministic upper bound known for this problem was O(nm(1/3) log m log sigma) for a general alphabet Sigma, where sigma = min(m, \Sigma\). Our reduction provides a solution to the pattern matching with swaps problem in time 0 (n log m log a). (C) 2002 Elsevier Science (USA). All rights reserved.

关键词： design and analysis of algorithms combinatorial algorithms on words pattern matching pattern matching with swaps non-standard pattern matching

来源：评论

学校读者我要写书评

暂无评论

OPTIMAL PARALLEL DETECTION OF SQUARES IN STRINGS

引用

ALGORITHMICA 1992年第4期8卷 285-319页

作者： APOSTOLICO, A UNIV LAQUILA DIPARTIMENTO MATEMAT PURA & APPLI-67100 LAQUILAITALY

A string w is primitive if it is not a power of another string (i.e., writing w = v(k) implies k = 1. Conversely, w is a square if w = vv, with v a primitive string. A string x is square-free if it has no nonempty substring of the form ww. It is shown that the square-freedom of a string of n symbols over an arbitrary alphabet can be tested by a CRCW PRAM with n processors in O(log n) time and linear auxiliary space. If the cardinality of the input alphabet is bounded by a constant independent of the input size, then the number of processors can be reduced to n/log n without affecting the time complexity of this strategy. The fastest sequential algorithms solve this problem O(n log n) or O(n) time, depending on whether the cardinality of the input alphabet is unbounded or bounded, and either performance is known to be optimal within its class. More elaborate constructions lead to a CRCW PRAM algorithm for detecting, within the same n-processors bounds, all positioned squares in x in time O(log n) and using linear auxiliary space. The fastest sequential algorithms solve this problem in O(n log n) time, and such a performance is known to be optimal.

关键词： PARALLEL COMPUTATION combinatorial algorithms on words STRING MATCHING AVOIDABLE REGULARITIES SQUARES AND REPETITIONS IN A STRING

来源：评论

学校读者我要写书评

暂无评论

On the longest common prefix of suffixes in an inverse Lyndon factorization and other properties

引用

THEORETICAL COMPUTER SCIENCE 2021年 862卷 24-41页

作者： Bonizzoni, Paola Felice, Clelia De Zaccagnino, Rocco Zizza, Rosalba Univ Milano Bicocca Dipartimento Informat Sistemist & Comunicaz Viale Sarca 336 I-20126 Milan Italy Univ Salerno Dipartimento Informat Via Giovanni Paolo II 132 I-84084 Fisciano SA Italy

The Lyndon factorization of a word has been largely studied and recently variants of it have been introduced and investigated with different motivations. In particular, the canonical inverse Lyndon factorization ICFL(w) of a word w, introduced in [1], maintains the main properties of the Lyndon factorization since it can be computed in linear time and it is uniquely determined. In this paper we investigate new properties of this factorization with the aim of exploring their use in some classical queries on w. The main property we prove is related to a classical query on words. We prove that there are relations between the length of the longest common prefix (or longest common extension) lcp(x, y) of two different suffixes x, y of a word w and the maximum length M of two consecutive factors of ICFL(w). More precisely, M is an upper bound on the length of lcp(x, y). A main tool used in the proof of the above result is a property that we state for factors mi with nonempty borders in ICFL(w): a nonempty border of mi cannot be a prefix of the next factor m(i+1). Another interesting result relates sorting of global suffixes, i.e., suffixes of a word w, and sorting of local suffixes, i.e., suffixes of products of factors in ICFL(w). This is the counterpart for ICFL(w) of the compatibility property, proved in [2,3] for the Lyndon factorization. Roughly, the compatibility property allows us to extend the mutual order between suffixes of products of the (inverse) Lyndon factors to the suffixes of the whole word. The last property we prove focuses on the Lyndon factorizations of a word and its factors. It suggests that the Lyndon factorizations of two words sharing a common overlap could be used to capture the common overlap of these two words. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Lyndon words Lyndon factorization combinatorial algorithms on words

来源：评论

学校读者我要写书评

暂无评论

Approximate swapped matching

引用

INFORMATION PROCESSING LETTERS 2002年第1期83卷 33-39页

作者： Amir, A Lewenstein, M Porat, E Bar Ilan Univ Dept Math & Comp Sci IL-52900 Ramat Gan Israel Georgia Inst Technol Atlanta GA 30332 USA Weizmann Inst Sci IL-76100 Rehovot Israel

Let a text string T of n symbols and a pattern string P of m symbols from alphabet E be given. A swapped version P' of P is a length m string derived from P by a series of local swaps (i.e., p(l)' <-- p(l+1) and p(l+1)' <-- p(l)), where each element can participate in no more than one swap. The Pattern Matching with Swaps problem is that of finding all locations i of T for which there exists a swapped version P' of P with an exact matching of P' in location i of T. Recently, some efficient algorithms were developed for this problem. Their time complexity is better than the best known algorithms for pattern matching with mismatches. However, the Approximate Pattern Matching with Swaps problem was not known to be solved faster than the Pattern Matching with Mismatches problem. In the Approximate Pattern Matching with Swaps problem the output is, for every text location i where there is a swapped match of P, the number of swaps necessary to create the swapped version that matches location i. The fastest known method to-date is that of counting mismatches and dividing by two. The time complexity of this method is O(nrootm log m) for a general alphabet Sigma. In this paper we show an algorithm that counts the number of swaps at every location where there is a swapped matching in time O (n log m log sigma), where sigma = min(m, \Sigma\). Consequently, the total time for solving the approximate pattern matching with swaps problem is O(f (n, m) + n log m log sigma), where f (n, in) is the time necessary for solving the Pattern Matching with Swaps problem. Since f (n, in) was shown to be O(n log m log a) this means our algorithm's running time is O(n log m log Q). (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： design and analysis of algorithms combinatorial algorithms on words pattern matching pattern matching with swaps non-standard pattern matching approximate pattern matching

来源：评论

学校读者我要写书评

暂无评论

Real Two Dimensional Scaled Matching

引用

ALGORITHMICA 2009年第3期53卷 314-336页

作者： Amir, Amihood Butman, Ayelet Lewenstein, Moshe Porat, Ely Bar Ilan Univ Ramat Gan Israel Johns Hopkins Univ Baltimore MD USA Holon Acad Inst Technol Holon Israel

Scaled Matching refers to the problem of finding all locations in the text where the pattern, proportionally enlarged according to an arbitrary real-sized scale, appears. Scaled matching is an important problem that was originally inspired by Computer Vision. Finding a combinatorial definition that captures the concept of real scaling in discrete images has been a challenge in the pattern matching field. No definition existed that captured the concept of real scaling in discrete images, without assuming an underlying continuous signal, as done in the image processing field. We present a combinatorial definition for real scaled matching that scales images in a pleasing natural manner. We also present efficient algorithms for real scaled matching. The running times of our algorithms are as follows. For T, a two-dimensional nxn text array, and P, an mxm pattern array, we find in T all occurrences of P scaled to any real value in time O(nm (3)+n (2) mlog m).

关键词： Design and analysis of algorithms combinatorial algorithms on words Pattern matching Scaled pattern matching Approximate pattern matching Generalized pattern matching

来源：评论

学校读者我要写书评

暂无评论

Covering a string

引用

ALGORITHMICA 1996年第3期16卷 288-297页

作者： Iliopoulos, CS Moore, DWG Park, K CURTIN UNIV TECHNOL SCH COMPPERTHWA 6001AUSTRALIA SEOUL NATL UNIV DEPT COMP ENGNSEOUL 151742SOUTH KOREA

We consider the problem of finding the repetitive structures of a given string x. The period u of the string x grasps the repetitiveness of x, since x is a prefix of a string constructed by concatenations of u. We generalize the concept of repetitiveness as follows: A string w covers a string I if there is a superstring of x which is constructed by concatenations and superpositions of Lu. A substring w of x is called a seed of x if w covers x. we present an O (n log n)-time algorithm for finding all the seeds of a given string of length n.

关键词： combinatorial algorithms on words string algorithms periodicity of strings covering of strings partitioning

来源：评论

学校读者我要写书评

暂无评论

Faster query algorithms for the text fingerprinting problem

引用

INFORMATION AND COMPUTATION 2011年第7期209卷 1057-1069页

作者： Chan, Chi-Yuan Yu, Hung-I Hon, Wing-Kai Wang, Biing-Feng Natl Tsing Hua Univ Dept Comp Sci Hsinchu 30043 Taiwan

Let S be a string over a finite, ordered alphabet Sigma. For any substring S' of S. the set of distinct characters contained in S' is called its fingerprint. The text fingerprinting indexing problem is to construct a data structure for the string S in advance, so that on given any input subset C of Sigma, we can answer the following queries efficiently: (1) determine if C represents a fingerprint of some substrings in S;(2) find all maximal substrings of S whose fingerprint is C. The best known results solved these two queries in Theta(vertical bar Sigma vertical bar) and Theta(vertical bar Sigma vertical bar + K) time, respectively, where K is the number of maximal substrings. In this paper, we propose two improved algorithms for the text fingerprinting indexing problem. The first one solves the two queries in O(vertical bar C vertical bar logn) and O(vertical bar C vertical bar logn + K) time, respectively. For the second one, the query time complexities are further reduced to O(vertical bar C vertical bar log(vertical bar Sigma vertical bar/vertical bar C vertical bar)) and O(vertical bar C vertical bar log (vertical bar Sigma vertical bar/vertical bar C vertical bar) + K). Both results answer an open problem proposed by Amir et al. (C) 2011 Elsevier Inc. All rights reserved.

关键词： Fingerprints combinatorial algorithms on words Text indexing Patricia trie

来源：评论

学校读者我要写书评

暂无评论

Pattern matching with swaps

引用

JOURNAL OF algorithms-COGNITION INFORMATICS AND LOGIC 2000年第2期37卷 247-266页

作者： Amir, A Aumann, Y Landau, GM Lewenstein, M Lewenstein, N Bar Ilan Univ Dept Math & Comp Sci IL-52900 Ramat Gan Israel Georgia Inst Technol Atlanta GA 30332 USA Polytech Univ MetroTech Ctr 6 Dept Comp & Informat Sci Brooklyn NY 11201 USA Univ Haifa Dept Comp Sci IL-31905 Haifa Israel

Let a text string T of n symbols and a pattern string P of m symbols from alphabet Sigma be given. A swapped version T' of T is a length n string derived from T by a series of local swaps (i.e., t(l)' <-- t(l+1) and t(l+1)' <-- t(l)), where each element can participate in no more than one swap. The pattern matching with swaps problem is that of finding all locations i for which there exists a swapped version T' of T with an exact matching of P in location i of T'. It has been an open problem whether swapped matching can be done in less than O(nm) time. In this paper we show the first algorithm that solves the pattern matching with swaps problem in time o(nm). We present an algorithm whose time complexity is O(nm(1/3) log m log sigma) for a general alphabet Sigma, where sigma = min(m, \Sigma\). (C) 2000 Academic Press.

关键词： design and analysis of algorithms combinatorial algorithms on words pattern matching pattern matching with swaps nonstandard pattern matching

来源：评论

学校读者我要写书评

暂无评论

Approximate Pattern Matching with the L₁, L₂ and L∞ Metrics

引用

ALGORITHMICA 2011年第2期60卷 335-348页

作者： Lipsky, Ohad Porat, Ely Bar Ilan Univ Dept Comp Sci IL-52900 Ramat Gan Israel

Given an alphabet I ={1,2 pound,aEuro broken vertical bar,|I |} pound text string TaI pound (n) and a pattern string PaI pound (m) , for each i=1,2,aEuro broken vertical bar,n-m+1 define L (p) (i) as the p-norm distance when the pattern is aligned below the text and starts at position i of the text. The problem of pattern matching with L (p) distance is to compute L (p) (i) for every i=1,2,aEuro broken vertical bar,n-m+1. We discuss the problem for d=1,2,a. First, in the case of L (1) matching (pattern matching with an L (1) distance) we show a reduction of the string matching with mismatches problem to the L (1) matching problem and we present an algorithm that approximates the L (1) matching up to a factor of 1+epsilon, which has an O (1/epsilon 2nlogm log vertical bar Sigma vertical bar) run time. Then, the L (2) matching problem (pattern matching with an L (2) distance) is solved with a simple O(nlog m) time algorithm. Finally, we provide an algorithm that approximates the L (a) matching up to a factor of 1+epsilon with a run time of O (1/epsilon 2nlogm log vertical bar Sigma vertical bar). We also generalize the problem of String Matching with mismatches to have weighted mismatches and present an O(nlog (4) m) algorithm that approximates the results of this problem up to a factor of O(log m) in the case that the weight function is a metric.

关键词： Design and analysis of algorithms combinatorial algorithms on words Approximate string matching Hamming distance

来源：评论

学校读者我要写书评

暂无评论

Efficient special cases of Pattern Matching with Swaps

引用

INFORMATION PROCESSING LETTERS 1998年第3期68卷 125-132页

作者： Amir, A Landau, GM Lewenstein, M Lewenstein, N Bar Ilan Univ Dept Math & Comp Sci IL-52900 Ramat Gan Israel Univ Haifa Dept Comp Sci IL-31905 Haifa Israel Polytech Univ Dept Comp & Informat Sci Brooklyn NY 11201 USA

Let a text string T of n symbols and a pattern string P of m symbols from alphabet Sigma be given. A swapped version T' of T is a length n string derived from T by a series of local swaps (i.e., t(iota)' <-- t(iota+1) and t(iota+1)' <--t(iota)) where each element can participate in no more than one swap. The Pattern Matching with Swaps problem is that of finding all locations i for which there exists a swapped version T' of T where there is an exact matching of P at location i of T'. It was recently shown that the Pattern Matching with Swaps problem has a solution in time O(nm(1/3) log m log(2) sigma), where sigma = min(\Sigma\, m). We consider some interesting special cases of patterns, namely, patterns where there is no length-one run, i.e., there are no a, b, c epsilon Sigma where b not equal a and b not equal c and where the substring abe appears in the pattern. We show that for such patterns the Pattern Matching with Swaps problem can be solved in time O(n log(2) m). (C) 1998 Published by Elsevier Science B.V. All rights reserved.

关键词： design of algorithms analysis of algorithms combinatorial algorithms on words pattern matching pattern matching with swaps approximate pattern matching generalized pattern matching

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：