Content area
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.
Details
Key topics Powered by Web of Science® Description for Powered by Web of Science
Identifier / keyword
Title
Knuth–Morris–Pratt illustrated
Author
Journal of Functional Programming; Cambridge
Volume
34
Publication year
2024
Publication date
Jan 2024
Section
Functional Pearl
Place of publication
Cambridge
Country of publication
United Kingdom
Publication subject
ISSN
09567968
e-ISSN
14697653
Source type
Scholarly Journal
Language of publication
English
Document type
Journal Article
Publication history
Online publication date
2024-01-30
Milestone dates
2023-03-10 (Received); 2023-12-06 (Revised); 2023-12-10 (Accepted)
Publication history
First posting date
30 Jan 2024
ProQuest document ID
2919835034
Document URL
https://www.proquest.com/scholarly-journals/knuth-morris-pratt-illustrated/docview/2919835034/se-2?accountid=208611
Copyright
© The Author(s), 2024. Published by Cambridge University Press. This work is licensed under the Creative Commons Attribution License This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution and reproduction, provided the original article is properly cited. (the “License”). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.
Last updated
2024-08-27
Database
ProQuest One Academic