kmp

README

KMP

This is a KMP(Knuth–Morris–Pratt algorithm) implement and related string function Strstr and Strchr which using KMP feature inside.

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.

A chinese version How KMP work note is here

Install

go get github.com/kkdai/kmp

Usage

package main

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

func main() {
	
	//Using KMP
	fmt.Println(KMP("co", "cocacola"))
	//0, 4
	
	//Using Strstr
	fmt.Println(Strstr("cocacola", "co"))
	//0
	
	//Using Strchr
	fmt.Println(Strstr("cocacola", "co"))
	//4
}	

Inspired

• Knuth-Morris-Pratt algorithm
• 理解KMP算法
• String Matching: 各種演算法介紹
• youtube: Tutorial: The Knuth-Morris-Pratt (KMP) String Matching Algorithm
• youtube: Knuth–Morris–Pratt(KMP) Pattern Matching(Substring search)
• Regular Expression Matching with a Trigram Index

Project52

It is one of my project 52.

License

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

Documentation

Index

• Constants
• func KMP(haystack string, needle string) []int
• func Strchr(haystack string, needle string) int
• func Strstr(haystack string, needle string) int

Constants

const (
	//MaxArraySize Need modify this value if your pattern is much learger than 100
	MaxArraySize int = 100
)

Functions

func KMP

func KMP(haystack string, needle string) []int

KMP Return index list if target string contain want string

func Strchr

func Strchr(haystack string, needle string) int

Strchr :Returns a pointer to the last occurrence of string in the string str

func Strstr

func Strstr(haystack string, needle string) int

Strstr :Use kmp for strstr function