Abstract:
The paper describes an algorithm for computing longest common substrings of two strings $\alpha_1$ and $\alpha_2$ with one mismatch in $O(|\alpha_1||\alpha_2|)$ time and $O(|\alpha_1|)$ additional space. The algorithm always scans symbols of $\alpha_2$sequentially, starting from the first symbol. The RAM model of computation is used.