Computing the longest common substring with one mismatch
Maxim A. Babenko, Tatiana Starikovskaya · Problems of Information Transmission · 2011
The paper describes an algorithm for computing longest common substrings of two strings α 1 and α 2 with one mismatch in O(|α 1||α 2|) time and O(|α 1|) additional space. The algorithm always scans symbols of α 2 sequentially, starting from the first symbol. The RAM model of computation is used.