Reversible Programming: A Case Study of Two String-Matching Algorithms

作     者：Glück, Robert Yokoyama, Tetsuo 

作者机构：DIKU Department of Computer Science University of Copenhagen Denmark Dept. of Electronics and Communication Technology Nanzan University Japan 

出 版 物：《arXiv》 (arXiv)

年 卷 期：2022年

核心收录：

主　　题：String searching algorithms 

摘      要：String matching is a fundamental problem in algorithm. This study examines the development and construction of two reversible string-matching algorithms: a naive string-matching algorithm and the Rabin-Karp algorithm. The algorithms are used to introduce reversible computing concepts, beginning from basic reversible programming techniques to more advanced considerations about the injectivization of the polynomial hash-update function employed by the Rabin-Karp algorithm. The results are two clean input-preserving reversible algorithms that require no additional space and have the same asymptotic time complexity as their classic irreversible originals. This study aims to contribute to the body of reversible algorithms and to the discipline of reversible programming. Copyright © 2022, The Authors. All rights reserved.