16 Result(s)

Chapter and Conference Paper

Runs of Side-Sharing Tandems in Rectangular Arrays

A side-sharing tandem is a rectangular array that is composed of two adjacent non-overlap** occurrences of the same rectangular block. Furthering our understanding of side-sharing tandems should facilitate t...

Shoshana Marcus, Dina Sokol, Sarah Zelikovitz in Similarity Search and Applications (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

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

2D Lyndon Words and Applications

A Lyndon word is a primitive string which is lexicographically smallest among cyclic permutations of its characters. Lyndon words are used for constructing bases in free Lie algebras, constructing de Bruijn se...

Shoshana Marcus, Dina Sokol in Algorithmica (2017)

Reference Work Entry In depth

Approximate Tandem Repeats

Gregory Kucherov, Dina Sokol 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)

Living Reference Work Entry In depth

Approximate Tandem Repeats

Gregory Kucherov, Dina Sokol in Encyclopedia of Algorithms

Chapter and Conference Paper

On Two-Dimensional Lyndon Words

A Lyndon word is a primitive string which is lexicographically smallest among cyclic permutations of its characters. Lyndon words are used for constructing bases in free algebras, constructing de Bruijn sequen...

Shoshana Marcus, Dina Sokol in String Processing and Information Retrieval (2013)

Chapter and Conference Paper

Succinct 2D Dictionary Matching with No Slowdown

The dictionary matching problem seeks all locations in a given text that match any of the patterns in a given dictionary. Efficient algorithms for dictionary matching scan the text once, searching for all patt...

Shoshana Neuburger, Dina Sokol in Algorithms and Data Structures (2011)

Chapter and Conference Paper

Small-Space 2D Compressed Dictionary Matching

The dictionary matching problem seeks all locations in a text that match any of the patterns in a dictionary. In the compressed dictionary matching problem, the input is in compressed form. In this paper we intro...

Shoshana Neuburger, Dina Sokol in Combinatorial Pattern Matching (2010)

Reference Work Entry In depth

Approximate Tandem Repeats

Gregory Kucherov, Dina Sokol in Encyclopedia of Algorithms (2008)

Chapter and Conference Paper

Approximate Parameterized Matching

Two equal length strings s and s′, over alphabets Σ _s and Σ _s′, parameterize match if there exists a bijection π:Σ _{s ...}

Carmit Hazay, Moshe Lewenstein, Dina Sokol in Algorithms – ESA 2004 (2004)

Chapter and Conference Paper

Dynamic Text and Static Pattern Matching

In this paper, we address a new version of dynamic pattern matching. The dynamic text and static pattern matching problem is the problem of finding a static pattern in a text that is continuously being updated. T...

Amihood Amir, Gad M. Landau, Moshe Lewenstein, Dina Sokol in Algorithms and Data Structures (2003)