A data structure for approximate string searching
Roos, Fei Shi, Widmayer · 1994
Summary form only given. The problem of searching for approximate occurrences of a pattern in a set of strings is called the approximate string searching problem. The recent interest in this problem comes from DNA sequence analysis: whenever a sequence investigator determines a new sequence, one of the first things he must do is to compare it with all available sequences to see if it resembles something already known. The authors provide a data structure for approximate string searching and discuss the searching algorithm.>