結果

問題 No.430 文字列検索
コンテスト
ユーザー ccppjsrb
提出日時 2020-09-29 12:20:52
言語 Go
(1.23.4)
結果
AC  
実行時間 9 ms / 2,000 ms
コード長 4,899 bytes
コンパイル時間 11,385 ms
コンパイル使用メモリ 235,156 KB
実行使用メモリ 6,816 KB
最終ジャッジ日時 2024-11-10 00:47:07
合計ジャッジ時間 11,601 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import (
	"bufio"
	"bytes"
	"encoding/binary"
	"errors"
	"fmt"
	"index/suffixarray"
	"io"
	"os"
	"strconv"
)

func configure(scanner *bufio.Scanner) {
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1000005), 1000005)
}
func getNextString(scanner *bufio.Scanner) string {
	scanned := scanner.Scan()
	if !scanned {
		panic("scan failed")
	}
	return scanner.Text()
}
func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}
func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}
func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}
func main() {
	fp := os.Stdin
	wfp := os.Stdout
	extra := 0
	if os.Getenv("I") == "IronMan" {
		fp, _ = os.Open(os.Getenv("END_GAME"))
		extra = 100
	}
	scanner := bufio.NewScanner(fp)
	configure(scanner)
	writer := bufio.NewWriter(wfp)
	defer func() {
		r := recover()
		if r != nil {
			fmt.Fprintln(writer, r)
		}
		writer.Flush()
	}()
	solve(scanner, writer)
	for i := 0; i < extra; i++ {
		fmt.Fprintln(writer, "-----------------------------------")
		solve(scanner, writer)
	}
}
func solve(scanner *bufio.Scanner, writer *bufio.Writer) {
	s := getNextString(scanner)
	m := getNextInt(scanner)
	sa := NewSuffixArray(s)
	var ans int
	for i := 0; i < m; i++ {
		c := getNextString(scanner)
		r := fufufufu(c, s, sa)
		l := fufufu(c, s, sa)
		ans += r - l
	}
	fmt.Fprintln(writer, ans)
}
func fufufu(c, s string, sa []int) int {
	l := -1
	r := len(s)
	for l+1 < r {
		m := (l + r) >> 1
		less := func() bool {
			for i := 0; i < len(c); i++ {
				if sa[m]+i >= len(s) || c[i] > s[sa[m]+i] {
					return true
				}
				if c[i] < s[sa[m]+i] {
					return false
				}
			}
			return false
		}
		if less() {
			l = m
			continue
		}
		r = m
	}
	return r
}
func fufufufu(c, s string, sa []int) int {
	l := -1
	r := len(s)
	for l+1 < r {
		m := (l + r) >> 1
		less := func() bool {
			for i := 0; i < len(c); i++ {
				if sa[m]+i >= len(s) || c[i] > s[sa[m]+i] {
					return false
				}
				if c[i] < s[sa[m]+i] {
					return true
				}
			}
			return false
		}
		if less() {
			r = m
			continue
		}
		l = m
	}
	return r
}

// NewSuffixArray returns the suffix array of s
func NewSuffixArray(s string) []int {
	sa := suffixarray.New([]byte(s))
	var b bytes.Buffer
	sa.Write(&b)
	return readIndex(&b)
}
func readInt(r io.Reader, buf []byte) (int64, error) {
	_, err := io.ReadFull(r, buf[0:binary.MaxVarintLen64]) // ok to continue with error
	x, _ := binary.Varint(buf)
	return x, err
}
func readSlice(r io.Reader, buf []byte, data []int) (n int, err error) {
	// read buffer size
	var size64 int64
	size64, err = readInt(r, buf)
	if err != nil {
		return
	}
	if int64(int(size64)) != size64 || int(size64) < 0 {
		// We never write chunks this big anyway.
		return 0, errors.New("suffixarray: data too large")
	}
	size := int(size64)
	// read buffer w/o the size
	if _, err = io.ReadFull(r, buf[binary.MaxVarintLen64:size]); err != nil {
		return
	}
	// decode as many elements as present in buf
	for p := binary.MaxVarintLen64; p < size; n++ {
		x, w := binary.Uvarint(buf[p:])
		data[n] = int(x)
		p += w
	}
	return
}
func readIndex(r io.Reader) []int {
	// buffer for all reads
	bufSize := 16 << 10
	buf := make([]byte, bufSize)
	// read length
	n64, err := readInt(r, buf)
	if err != nil {
		return nil
	}
	if int64(int(n64)) != n64 || int(n64) < 0 {
		return nil
	}
	n := int(n64)
	// allocate space
	data := make([]byte, n)
	sa := make([]int, n)
	// read data
	if _, err := io.ReadFull(r, data); err != nil {
		return nil
	}
	// read index
	csa := sa
	for len(csa) > 0 {
		i, err := readSlice(r, buf, csa)
		if err != nil {
			return nil
		}
		csa = csa[i:]
	}
	return sa
}

// NewLcpArray returns the LCP array of s
func NewLcpArray(s string, sa []int) []int {
	n := len(s)
	rnk := make([]int, n)
	for i := 0; i < n; i++ {
		rnk[sa[i]] = i
	}
	lcp := make([]int, n-1)
	h := 0
	for i := 0; i < n; i++ {
		if h > 0 {
			h--
		}
		if rnk[i] == 0 {
			continue
		}
		for j := sa[rnk[i]-1]; j+h < n && i+h < n; h++ {
			if s[j+h] != s[i+h] {
				break
			}
		}
		lcp[rnk[i]-1] = h
	}
	return lcp
}

//NewZAlgorithm returns the array of length n, such that the i-th element is the length of the LCP (Longest Common Prefix) of s[0..n) and s[i..n).
func NewZAlgorithm(s string) []int {
	n := len(s)
	s2 := make([]int, n)
	for i := 0; i < n; i++ {
		s2[i] = int(s[i])
	}
	return zAlgorithm(s2)
}
func zAlgorithm(s []int) []int {
	n := len(s)
	z := make([]int, n)
	if n == 0 {
		return z
	}
	j := 0
	for i := 1; i < n; i++ {
		k := &z[i]
		switch {
		case j+z[j] <= i:
			*k = 0
		case j+z[j]-i > z[i-j]:
			*k = z[i-j]
		default:
			*k = j + z[j] - i
		}
		for i+*k < n && s[*k] == s[i+*k] {
			*k++
		}
		if j+z[j] < i+z[i] {
			j = i
		}
	}
	z[0] = n
	return z
}
0