結果

問題 No.430 文字列検索
コンテスト
ユーザー Ogtsn99
提出日時 2025-03-28 01:50:36
言語 Go
(1.23.4)
結果
AC  
実行時間 1,379 ms / 2,000 ms
コード長 1,978 bytes
コンパイル時間 13,147 ms
コンパイル使用メモリ 237,828 KB
実行使用メモリ 7,324 KB
最終ジャッジ日時 2025-03-28 01:51:00
合計ジャッジ時間 23,747 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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
}

type BM struct {
	pattern string
	table   [256]int
}

func NewBM(pattern string) *BM {
	var tbl [256]int
	for i := 0; i < 256; i++ {
		tbl[i] = -1
	}
	for i := 0; i < len(pattern); i++ {
		tbl[pattern[i]] = i
	}
	return &BM{pattern, tbl}
}

func (b *BM) Count(s string) int {
	ps := len(b.pattern)
	if ps == 0 {
		return 0
	}
	ss := len(s)
	if ps > ss {
		return 0
	}
	c := 0
	i := 0
	for i+ps <= ss {
		j := ps - 1
		for j >= 0 && s[i+j] == b.pattern[j] {
			j--
		}
		if j < 0 {
			c++
			i++
		} else {
			skip := j - b.table[s[i+j]]
			if skip < 1 {
				skip = 1
			}
			i += skip
		}
	}
	return c
}

func (b *BM) FindAll(s string) []int {
	ps := len(b.pattern)
	if ps == 0 {
		return nil
	}
	ss := len(s)
	if ps > ss {
		return nil
	}
	var res []int
	i := 0
	for i+ps <= ss {
		j := ps - 1
		for j >= 0 && s[i+j] == b.pattern[j] {
			j--
		}
		if j < 0 {
			res = append(res, i)
			i++
		} else {
			skip := j - b.table[s[i+j]]
			if skip < 1 {
				skip = 1
			}
			i += skip
		}
	}
	return res
}

// ==============================================================
// 提示の solve() 関数
// ==============================================================
func solve() {
	s := ns() // 検索対象文字列
	n := ni() // 検索回数

	ans := 0
	for i := 0; i < n; i++ {
		t := ns() // パターン
		bm := NewBM(t)
		ans += len(bm.FindAll(s))
	}
	fmt.Println(ans)
}

// 提出時には main 関数で solve() を呼ぶ
func main() {
	defer wtr.Flush()
	solve()
}
0