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 }