quick search

quick-search.go

package main

import (
	"bufio"
	"fmt"
	"os"
	"strings"
)

const SIGMA = 256

func native(ts, ps []string) {
	n := len(ts)
	m := len(ps)

	if n == 0 || m == 0 {
		return
	}

	for i := 0; i <= n-m; i++ {
		j := 0
		for j = 0; j < m && ps[j] == ts[i+j]; {
			j++
		}
		if j == m {
			fmt.Println(i)
		}
	}
}

func quickSearch(ts, ps []string) {
	n := len(ts)
	m := len(ps)

	if n == 0 || m == 0 {
		return
	}

	// 要素数+1を参照するため
	ts = append(ts, "")

	// 移動表
	shift := make(map[string]int)
	for i := 0; i < m; i++ {
		shift[ps[i]] = m - i
	}

	for i := 0; i <= n-m; {
		j := 0
		for j = 0; j < m && ps[j] == ts[i+j]; j++ {
		}

		if j == m {
			fmt.Println(i)
		}

		if shift[ts[i+m]] != 0 {
			i += shift[ts[i+m]]
		} else {
			i += m
		}
	}
}

func main() {
	var t, p string
	var sc = bufio.NewScanner(os.Stdin)
	if sc.Scan() {
		t = sc.Text()
	}
	if sc.Scan() {
		p = sc.Text()
	}

	ts := strings.Split(t, "")
	ps := strings.Split(p, "")

	fmt.Println("===== NATIVE =====")
	native(ts, ps)

	fmt.Println("===== QS =====")
	quickSearch(ts, ps)
}