Before revision:  For the gap edit distance problem, we give a greedy algorithm that distinguishes in time O(n{k}+k^2)  between length-n input strings with edit distance at most k and those with edit distance more than 4k^2 .
After revision:  For the gap edit distance problem, we give an O(n{k}+k^2) between length-n input strings with edit distance at most k and those with edit distance more than 4k^2 .