activity
20152026
most citedStreaming Algorithms For Computing Edit Distance Without Exploiting Suffix Trees

9 citations · 10 across the 19 of their papers we have counts for

collaborators
Showing 2018Show all

2 papers · 1 filter

cs.DS2018

Approximate Online Pattern Matching in Sub-linear Time

Diptarka Chakraborty, Debarati Das, Michal Koucky

We consider the approximate pattern matching problem under edit distance. In this problem we are given a pattern of length and a text of length over some alphabet $…

cs.DS2018

Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time

Diptarka Chakraborty, Debarati Das, Elazar Goldenberg +2

Edit distance is a measure of similarity of two strings based on the minimum number of character insertions, deletions, and substitutions required to transform one string into the…