package main import ( "bufio" "fmt" "os" "strconv" ) // ============================================================== // 入力高速化用の共通処理 (AtCoder等で利用する想定) // ============================================================== var ( sc = bufio.NewScanner(os.Stdin) wtr = bufio.NewWriter(os.Stdout) ) func init() { sc.Split(bufio.ScanWords) } func ns() string { sc.Scan() return sc.Text() } func ni() int { sc.Scan() v, _ := strconv.Atoi(sc.Text()) return v } //============================================================== // ここから Boyer-Moore 実装 //============================================================== // boyerMooreGalil は文字列 s において、パターン t がマッチするすべての開始インデックスを返す func boyerMooreGalil(s, t string) []int { ls, lt := len(s), len(t) if lt == 0 { // パターンが空文字の場合、慣習上 0 を返す・もしくは全部にマッチとするか等は状況に応じて // ここでは全ての位置にマッチするとすると膨大な配列が返るため、通常は特殊ケースを避ける // solve()の使い方的に空文字は来ない前提ならここで return nil などでもよい return nil } if lt > ls { return nil } // ずらし量を事前に計算するテーブルの構築 slide := calculateSlideTable(t) var res []int i := 0 for i+lt <= ls { j := lt - 1 // 後ろから比較して不一致を探す for j >= 0 && s[i+j] == t[j] { j-- } if j < 0 { // マッチが見つかった res = append(res, i) // BM(Galil) の最適化としては色々あるが、簡易的に1つ進める i += 1 } else { // ずらし量の計算 skip := j - slide[s[i+j]] if skip < 1 { skip = 1 } i += skip } } return res } // calculateSlideTable は Boyer-Moore 法のずらし量計算に使うテーブルを構築する // ここではベタに 256 文字分の配列を用意しています (ASCII想定) func calculateSlideTable(pattern string) [256]int { var table [256]int // 最初はすべて -1 for i := 0; i < 256; i++ { table[i] = -1 } // パターン中の文字が最後に登場する場所を格納 for i := 0; i < len(pattern); i++ { table[pattern[i]] = i } return table } // ============================================================== // 提示の solve() 関数 // ============================================================== func solve() { s := ns() // 検索対象文字列 n := ni() // 検索回数 ans := 0 for i := 0; i < n; i++ { t := ns() // パターン // s 中でパターン t が出現する回数をカウント ans += len(boyerMooreGalil(s, t)) } fmt.Println(ans) } // 提出時には main 関数で solve() を呼ぶ func main() { defer wtr.Flush() solve() }