Streaming k-edit approximate pattern matching via string decomposition

05/01/2023

∙

by   Sudatta Bhattacharya, et al.

∙

0

∙

share

In this paper we give an algorithm for streaming k-edit approximate pattern matching which uses space O(k^2) and time O(k^2) per arriving symbol. This improves substantially on the recent algorithm of Kociumaka, Porat and Starikovskaya (2022) which uses space O(k^5) and time O(k^8) per arriving symbol. In the k-edit approximate pattern matching problem we get a pattern P and text T and we want to identify all substrings of the text T that are at edit distance at most k from P. In the streaming version of this problem both the pattern and the text arrive in a streaming fashion symbol by symbol and after each symbol of the text we need to report whether there is a current suffix of the text with edit distance at most k from P. We measure the total space needed by the algorithm and time needed per arriving symbol.