paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Knuth–Morris–Pratt illustrated

图解 Knuth–Morris–Pratt
JFP vol.342024匹配度 1/10 · 该论文是关于 KMP 字符串搜索算法的函数式编程教学推导,重点在算法讲解与函数式编程技巧,与用户关注的静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析均无直接关系。引用 0 inbox
CAMERON MOY
crossref: 2026-09-10

AI 速览

一句话:用函数式编程技巧逐步图解推导 KMP 字符串搜索算法,降低理解难度。

KMP(Knuth–Morris–Pratt)字符串搜索算法素来难以理解,许多解释淹没在索引算术中,反而掩盖了算法本质。本文采用增量式构造方式,借助图示逐步展示 KMP 的推导过程,并仅使用初等的函数式编程技巧来完成这一推导。通过把每一步的动机和结构可视化,论文使最终算法更容易理解。摘要未报告实验评估或形式化验证,其贡献主要在于教学性阐释与可理解性提升。

问题
KMP 字符串搜索算法难以理解,现有解释常陷入索引算术,掩盖其核心思想。
方法
采用增量式构造,用图示逐步展示 KMP 的推导,并仅使用初等函数式编程技巧。
评估
以教学性阐释评估可理解性,说明最终结果更易理解;摘要未报告实验或形式化评估。
原文摘要(Abstract)

Abstract The Knuth–Morris–Pratt (KMP) algorithm for string search is notoriously difficult to understand. Lost in a sea of index arithmetic, most explanations of KMP obscure its essence. This paper constructs KMP incrementally, using pictures to illustrate each step. The end result is easier to comprehend. Additionally, the derivation uses only elementary functional programming techniques.

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@article{paperbot2683,
  title = {Knuth–Morris–Pratt illustrated},
  author = {CAMERON MOY},
  journal = {Journal of Functional Programming},
  volume = {34},
  year = {2024},
  doi = {10.1017/s0956796824000017}
}