Knuth-Morris-Pratt Algorithm

[EN]
Implementation of the Knuth-Morris-Pratt algorithm or KMP algorithm in GO.

Knuth-Morris-Pratt is a substring search algorithm.

[FR]
Implémentation de l'algorithme de Knuth-Morris-Pratt ou l'algorithme KMP en Go.

Knuth-Morris-Pratt est un algorithme de recherche de sous-chaîne.

Technology

• go
• ginkgo

Usage

CLI:

go test -v test/

CODE:

import kmp "github.com/fbonhomm/knuth-morris-pratt/source"

var index, length int
var buffer = []byte("abc abcdab abcdabcdabde")
var pattern = []byte("abcdabd") // 7
var pattern1 = []byte("abcdabdr") // 8

index = kmp.Search(buffer, pattern) // 15
index = kmp.Search(buffer, pattern1) // -1

Explanations

• English
• Français

Links

https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm https://dev.to/girish3/string-matching-kmp-algorithm-cie
https://www.geeksforgeeks.org/kmp-algorithm-for-pattern-searching/