Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package main
- import (
- "flag"
- "fmt"
- "os"
- )
- func makeTable(word string) ([]int) {
- table := make([]int, len(word))
- pos := 2
- cnd := 0 // candidate substring
- table[0] = -1; table[1] = 0
- for pos < len(word) {
- if word[pos - 1] == word[cnd] {
- table[pos] = cnd + 1
- pos += 1
- cnd += 1
- } else if cnd > 0 {
- cnd = table[cnd]
- } else {
- table[pos] = 0
- pos += 1
- }
- }
- return table
- }
- func search(word string, text string) int {
- m := 0
- i := 0
- table := makeTable(word)
- for (m+i) < len(text) {
- if word[i] == text[i+m] {
- i += 1
- if i == len(word) {
- return m
- }
- } else {
- m = m + i - table[i]
- if table[i] > -1 {
- i = table[i]
- } else {
- i = 0
- }
- }
- }
- return -1
- }
- func main() {
- flag.Parse()
- if (len(flag.Args()) != 2) {
- fmt.Fprintf(os.Stderr, "Usage: kmp WORD TEXT_TO_SEARCH_IN\n")
- os.Exit(1)
- }
- word := flag.Arg(0)
- text := flag.Arg(1)
- index := search(word, text)
- println(index)
- if index < 0 { os.Exit(1) } else { os.Exit(0) }
- }
Add Comment
Please, Sign In to add comment