rabinkarp

Documentation

Overview

Package rabinkarp provides the Rabin-Karp string pattern matching algorithm.

Example

package main

import (
	"fmt"
	"rabinkarp"
	"sort"
)

func main() {
	pattern := "bro"
	inputs := []string{"slowbro", "browser", "bob", "st", "bebrobaum"}
	matcher := rabinkarp.Make(rabinkarp.NaiveHasher)
	matches := matcher.MatchAll(pattern, inputs)

	sort.Sort(matches)
	fmt.Println(matches)

}

Output:
[{0 browser} {2 bebrobaum} {4 slowbro}]

Index

• Constants
• Variables
• type Hasher
• type Match
• type Matches
  • func (m Matches) Len() int
  • func (m Matches) Less(i, j int) bool
  • func (m Matches) Swap(i, j int)
• type RabinKarp
  • func Make(h Hasher) RabinKarp
  • func (f RabinKarp) MatchAll(p string, v []string) Matches

Examples

• Package

Constants

const (
	NaiveHasher = naiveHasher(0)
)

Variables

var DefaultMatcher = Make(NaiveHasher)

DefaultMatcher provides a instance of RabinKarp with the naive hasher implementation.

Types

type Hasher

type Hasher interface {
	Hash(string) int
}

Hasher is used to hash values in a RabinKarp func

type Match

type Match struct {
	Index uint
	Value string
}

Match is return when a RabinKarp function founds a match

type Matches

type Matches []Match

Matches is a slice of match. The type implements sort.Interface

func (Matches) Len

func (m Matches) Len() int

func (Matches) Less

func (m Matches) Less(i, j int) bool

func (Matches) Swap

func (m Matches) Swap(i, j int)

type RabinKarp

type RabinKarp func(string, string) (bool, Match)

RabinKarp is a function that runs the rabin karp algorithm

func Make

func Make(h Hasher) RabinKarp

Make a closure of RabinKarp which uses the specified hasher.

func (RabinKarp) MatchAll

func (f RabinKarp) MatchAll(p string, v []string) Matches

MatchAll runs RabinKarp on every string in the slice and stores all pattern matches in a matches slice and returns it.