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

Gist に残した: quick search · GitHub

参考記事

www.m3tech.blog

www.nct9.ne.jp