In computer science, the Knuth–Morris–Pratt string searching algorithm (or KMP algorithm) searches for occurrences of a "word" W within a main "text string" S by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters.

reference wikipedia

Time complexity O(M+N),

Space complexity O(N)

go get github.com/yc0/kmp

package main

import (
  "fmt"
  "github.com/yc0/kmp"
)

func main() {
  fmt.Println(kmp("cocacola", "co"))
  //0, 4
  fmt.Println(kmp("abxabcabcabyaaababcabyb", "abcaby"))
  //6, 16
}	

https://www.youtube.com/watch?v=GTJr8OvyEVQ

This package is licensed under MIT license. See LICENSE for details.