Quasi-linear-time substring searching by q-gram distance

摘要

The q-gram distance dq(x, y) between two strings x and y is a string similarity measure correlated with a famous string distance: the edit distance. In addition, it can be computed much faster, in linear (O(|x|+|y|)) time, than the edit distance in quadratic (O(|x||y|)) time, where | · | denotes the string length. However, it does not mean that we can find all substrings of a text t similar to a pattern p in linear time. In this paper we will propose a searching algorithm achieving quasi-linear (O(|t| log |p| + |p|)) time by the q-gram distance.