RUS  ENG
Full version
JOURNALS // Problemy Peredachi Informatsii // Archive

Probl. Peredachi Inf., 2011 Volume 47, Issue 1, Pages 33–39 (Mi ppi2035)

This article is cited in 8 papers

Large Systems

Computing the longest common substring with one mismatch

M. A. Babenko, T. A. Starikovskaya

Chair of Mathematical Logic and Theory of Algorithms, Faculty of Mechanics and Mathematics, Lomonosov Moscow State University

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.

UDC: 621.391.15+519.1

Received: 07.05.2010
Revised: 24.08.2010


 English version:
Problems of Information Transmission, 2011, 47:1, 28–33

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024