论文标题
可逆编程：两种字符串匹配算法的案例研究
Reversible Programming: A Case Study of Two String-Matching Algorithms
论文作者
论文摘要
弦匹配是算法中的基本问题。这项研究研究了两种可逆的弦乐匹配算法的开发和构建：一种幼稚的弦匹配算法和Rabin-Karp算法。该算法用于引入可逆的计算概念，从基本可逆编程技术开始，再到关于Rabin-Karp算法使用的多项式伸缩函数的注射范围的更高级考虑。结果是两个干净的输入可逆算法，这些算法不需要额外的空间，并且具有与经典不可逆的原件相同的渐近时间复杂性。这项研究旨在为可逆算法和可逆编程的纪律做出贡献。
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.
