The Knuth–Morris–Pratt string searching algorithm

kmp.go

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) }
}