Skip to content
Aho–Corasick algorithm automation implement in Golang
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
.gitignore
README.md
aca.go
aca_test.go
node.go

README.md

ACA: Aho–Corasick Automation

GitHub license GoDoc Build Status

Aho–Corasick algorithm

In computer science, the Aho–Corasick algorithm is a string searching algorithm invented by Alfred V. Aho and Margaret J. Corasick.[1] It is a kind of dictionary-matching algorithm that locates elements of a finite set of strings (the "dictionary") within an input text. It matches all strings simultaneously. The complexity of the algorithm is linear in the length of the strings plus the length of the searched text plus the number of output matches. Note that because all matches are found, there can be a quadratic number of matches if every substring matches (e.g. dictionary = a, aa, aaa, aaaa and input string is aaaa).

(from Wiki)

Explanation in Chinese

Check this blog for more detail explanation, but it is Chinese

Install

go get github.com/kkdai/aca

Usage

package main

import (
	"fmt"

	. "github.com/kkdai/aca"
)

func main() {
	ac := NewACA()
	ac.Insert("say")
	ac.Insert("she")
	ac.Insert("shell")
	ac.Insert("shr")
	ac.Insert("her")
	ac.BuildAC()
	fmt.Println(ac.Query("aaashellaashrmmmmmhemmhera"))
	//[shell, shr, her]
}

Inspired

Project52

It is one of my project 52.

License

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

You can’t perform that action at this time.