- Educational
This project is an implementation of various string matching algorithms described
in Introduction to algorithms
- Brute force
- Rabin Karp
- DFA (Deterministic finite automaton)
- Knuth Morris Pratt
- n = length of the input text
- m = length of the pattern
- This table shows the worst case time
Algorithms | Preprocessing time | Matching time |
---|---|---|
Brute Force | 0 | Ο((n - m + 1)m) |
Rabin Karp | Θ(m) | Ο((n - m + 1)m) |
DFA | Ο(m |Σ|) | Θ(n) |
Knuth Morris Pratt | Θ(m) | Θ(n) |
The problem of finding occurrence(s) of a pattern string within another string or body of text. The algorithm returns an array of the first index for every occurrence in the text
package main
import (
"fmt"
"log"
"string-matching/internal/KMP"
)
func main() {
input := `Project Gutenberg's International Short Stories: French, by Various
This eBook is for the use of anyone anywhere at no cost and with
almost no restrictions whatsoever. You may copy it, give it away or
re-use it under the terms of the Project Gutenberg License included
with this eBook or online at www.gutenberg.net
`
pattern := "Gutenberg"
indexes, err := KMP.MatchString(input, pattern)
if err != nil {
log.Fatal(err)
}
printMatches(indexes, input, len(pattern))
}
func printMatches(indexes []int, input string, patternLen int) {
for _, index := range indexes {
fmt.Printf("found at %d, %s\n", index, input[index:index+patternLen])
}
}
found at 8, Gutenberg
found at 244, Gutenberg
- Clone the repo
git clone https://github.com/Leonardpepa/string-matching-go.git
- Build
go build
- run on windows
string-matching.exe
- run on linux
./string-matching
- run tests
go test