5 papers
Improved Circular -Mismatch Sketches
Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz +2
The shift distance between two strings and of the same length is defined as the minimum Hamming distance between and any rotation (cyclic s…
Time-Space Tradeoffs for Finding a Long Common Substring
Stav Ben-Nun, Shay Golan, Tomasz Kociumaka +1
We consider the problem of finding, given two documents of total length , a longest string occurring as a substring of both documents. This problem, known as the Longest Common…
The Streaming k-Mismatch Problem: Tradeoffs between Space and Total Time
Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz +1
We revisit the -mismatch problem in the streaming model on a pattern of length and a streaming text of length , both over a size- alphabet. The current state-of-the-ar…
Approximating Text-to-Pattern Hamming Distances
Timothy M. Chan, Shay Golan, Tomasz Kociumaka +2
We revisit a fundamental problem in string matching: given a pattern of length m and a text of length n, both over an alphabet of size , compute the Hamming distance between the…
Locally Consistent Parsing for Text Indexing in Small Space
Or Birenzwige, Shay Golan, Ely Porat
We consider two closely related problems of text indexing in a sub-linear working space. The first problem is the Sparse Suffix Tree (SST) construction of a set of suffixes usi…