2018/01/28 by Przemysław Uznański, Uznański, Przemysław
Computer Science · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1801.09159
openalex publication_date 2018/01/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The problem of finding distance between pattern of length m and text of length n is a typical way of generalizing pattern matching to incorporate dissimilarity score. For both Hamming and L1 distances only a super linear upper bound \widetildeO(n√(m)) are known, which prompts the question of relaxing the problem: either by asking for (1 ± ε) approximate distance (every distance is reported up to a multiplicative factor), or k-approximated distance (distances exceeding k are reported as ∞). We focus on L1 distance, for which we show new algorithms achieving complexities respectively \widetildeO(ε-1 n) and \widetildeO((m+k√(m)) ⋅ n/m). This is a significant improvement upon previous algorithms with runtime \widetildeO(ε-2 n) of Lipsky and Porat [Algorithmica 2011] and \widetildeO(n√(k)) of Amir, Lipsky, Porat and Umanski [CPM 2005].