結果

問題 No.430 文字列検索
コンテスト
ユーザー Ogtsn99
提出日時 2025-03-28 01:06:36
言語 Go
(1.23.4)
結果
AC  
実行時間 1,280 ms / 2,000 ms
コード長 2,847 bytes
コンパイル時間 13,785 ms
コンパイル使用メモリ 244,568 KB
実行使用メモリ 7,328 KB
最終ジャッジ日時 2025-03-28 01:07:01
合計ジャッジ時間 22,291 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

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