90 Result(s)

Chapter and Conference Paper

On Suffix Tree Detection

A suffix tree is a fundamental data structure for string processing and information retrieval, however, its structure is still not well understood. The suffix trees reverse engineering problem, which its research...

Amihood Amir, Eitan Kondratovsky… in String Processing and Information Retrieval (2023)

Article

Double String Tandem Repeats

A tandem repeat is an occurrence of two adjacent identical substrings. In this paper, we introduce the notion of a double string, which consists of two parallel strings, and we study the problem of locating all t...

Amihood Amir, Ayelet Butman, Gad M. Landau, Shoshana Marcus, Dina Sokol in Algorithmica (2023)

Article

Multidimensional Period Recovery

Multidimensional data are widely used in real-life applications. Intel’s new brand of SSDs, called 3D XPoint, is an example of three-dimensional data. Motivated by a structural analysis of multidimensional dat...

Amihood Amir, Ayelet Butman, Eitan Kondratovsky, Avivit Levy, Dina Sokol in Algorithmica (2022)

Chapter and Conference Paper

Reconstructing Parameterized Strings from Parameterized Suffix and LCP Arrays

Reconstructing input from a data structure entails determining whether an instance of the data structure is in fact valid or not, and if valid, discovering the underlying data that it represents. In this paper...

Amihood Amir, Concettina Guerra… in String Processing and Information Retrieval (2022)

Chapter and Conference Paper

Adaptive Exact Learning in a Mixed-Up World: Dealing with Periodicity, Errors and Jumbled-Index Queries in String Reconstruction

We study the query complexity of exactly reconstructing a string from adaptive queries, such as substring, subsequence, and jumbled-index queries. Such problems have applications, e.g., in computational biolog...

Ramtin Afshar, Amihood Amir… in String Processing and Information Retrieval (2020)

Chapter and Conference Paper

Approximating the Anticover of a String

The k-anticover of a string S is a set of distinct k-length substrings such that every index in S is contained in one of these substrings. The existence of an anticover indicates a lack of structure in S. It was ...

Amihood Amir, Itai Boneh, Eitan Kondratovsky in String Processing and Information Retrieval (2020)

Chapter and Conference Paper

Multidimensional Period Recovery

Multidimensional data are widely used in real-life applications. Intel’s new brand of SSDs, called 3D XPoint, is an example of three-dimensional data. Motivated by a structural analysis of multidimensional dat...

Amihood Amir, Ayelet Butman… in String Processing and Information Retrieval (2020)

Article

Can We Recover the Cover?

Data analysis typically involves error recovery and detection of regularities as two different key tasks. In this paper we show that there are data types for which these two tasks can be powerfully combined. A co...

Amihood Amir, Avivit Levy, Moshe Lewenstein, Ronit Lubin, Benny Porat in Algorithmica (2019)

Article

Mind the Gap!

We examine the complexity of the online Dictionary Matching with One Gap Problem (DMOG) which is the following. Preprocess a dictionary D of d patterns, where each pattern contains a special gap symbol that can m...

Amihood Amir, Tsvi Kopelowitz, Avivit Levy, Seth Pettie, Ely Porat… in Algorithmica (2019)

Chapter and Conference Paper

Finding Periods in Cartesian Tree Matching

In Cartesian tree matching, two strings match if the Cartesian trees of the strings are the same. In this paper we define full, initial, and general periods in Cartesian tree matching, and present an O(n) time al...

Magsarjav Bataa, Sung Gwan Park, Amihood Amir, Gad M. Landau… in Combinatorial Algorithms (2019)

Chapter and Conference Paper

Searching for a Modified Pattern in a Changing Text

Much attention has been devoted recently to the dynamic model of pattern matching. In this model the input is updated or changed locally. One is interested in obtaining the appropriate search result in time th...

Amihood Amir, Eitan Kondratovsky in String Processing and Information Retrieval (2018)

Article

On Representations of Ternary Order Relations in Numeric Strings

Order-preserving matching is a string matching problem of two numeric strings where the relative orders of consecutive substrings are matched instead of the characters themselves. The order relation between tw...

**il Kim, Amihood Amir, Joong Chae Na, Kunsoo Park… in Mathematics in Computer Science (2017)

Chapter and Conference Paper

Longest Common Factor After One Edit Operation

It is well known that the longest common factor (LCF) of two strings over an integer alphabet can be computed in time linear in the total length of the two strings. Our aim here is to present an algorithm that...

Amihood Amir, Panagiotis Charalampopoulos… in String Processing and Information Retrieval (2017)

Article

Configurations and Minority in the String Consensus Problem

The Closest String Problem is defined as follows. Let \(S\) S ...

Amihood Amir, Haim Paryenty, Liam Roditty in Algorithmica (2016)

Reference Work Entry In depth

Two-Dimensional Scaled Pattern Matching

Amihood Amir in Encyclopedia of Algorithms (2016)

Reference Work Entry In depth

Similarity Between Compressed Strings

** Wook Kim, Amihood Amir, Gad M. Landau, Kunsoo Park in Encyclopedia of Algorithms (2016)

Reference Work Entry In depth

Multidimensional Compressed Pattern Matching

Amihood Amir in Encyclopedia of Algorithms (2016)

Chapter and Conference Paper

Period Recovery over the Hamming and Edit Distances

A string S of length n has period P of length p if \(S[i]=S[i+p]\) ...

Amihood Amir, Mika Amit, Gad M. Landau, Dina Sokol in LATIN 2016: Theoretical Informatics (2016)