Approximate string searching with fast fourier transforms and simplexes
Daniel Liu · 2019
Previous algorithms for solving the approximate string matching with Hamming distance problem with wildcard ("don't care") characters have been shown to take \(O(|\Sigma| N \log M)\) time, where \(N\) is the length of the text, \(M\) is the length of the pattern, and \(|\Sigma|\) is the size of the alphabet. They make use of the Fast Fourier Transform for efficiently calculating convolutions. We describe a novel approach of the problem, which makes use of special encoding schemes that depend on \((|\Sigma| - 1)\)-simplexes in \((|\Sigma| - 1)\)-dimensional space.