7 citations · 15 across the 15 of their papers we have counts for
17 papers · 1 filter
Explicit Combinatoric Structures of Palindromes and Chromatic Number of Restriction Graphs
Amihood Amir, Michael Itzhaki
The palindromic fingerprint of a string is the set . In this work, w…
On the Practical Power of Automata in Pattern Matching
Ora Amir, Amihood Amir, Aviezri Fraenkel +1
The classical pattern matching paradigm is that of seeking occurrences of one string - the pattern, in another - the text, where both strings are drawn from an alphabet set . As…
Dynamic Suffix Array with Sub-linear update time and Poly-logarithmic Lookup Time
Amihood Amir, Itai Boneh
The Suffix Array of an -length string is a lexicographically sorted array of the suffixes of . The suffix array is one of the most well known and widely…
The k-mappability problem revisited
Amihood Amir, Itai Boneh, Eitan Kondratovsky
The -mappability problem has two integers parameters and . For every subword of size in a text , we wish to report the number of indices in in which the word o…
Update Query Time Trade-off for dynamic Suffix Arrays
Amihood Amir, Itai Boneh
The Suffix Array SA(S) of a string S[1 ... n] is an array containing all the suffixes of S sorted by lexicographic order. The suffix array is one of the most well known indexing da…
Adaptive Exact Learning in a Mixed-Up World: Dealing with Periodicity, Errors and Jumbled-Index Queries in String Reconstruction
Ramtin Afshar, Amihood Amir, Michael T. Goodrich +1
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,…