/* URL: https://yukicoder.me/problems/no/430 */ package main import ( "bufio" "fmt" "io" "math" "os" "sort" "strconv" ) var ( S string m int C []string ) func main() { defer stdout.Flush() S = reads() m = readi() for i := 0; i < m; i++ { C = append(C, reads()) } tsa := SuffixArrayString(S) ans := 0 for i := 0; i < m; i++ { pattern := C[i] l, r := MatchBySA(S, tsa, pattern) ans += max(0, r-l+1) } fmt.Println(ans) } // originated from: // https://qiita.com/EmptyBox_0/items/2f8e3cf7bd44e0f789d5#strings // https://atcoder.github.io/ac-library/production/document_ja/string.html func SuffixArrayString(s string) []int { n := len(s) s2 := make([]int, n) for i := 0; i < n; i++ { s2[i] = int(s[i]) } return _saIs(s2, 255) } func LcpArrayString(s string, sa []int) []int { n := len(s) s2 := make([]int, n) for i := 0; i < n; i++ { s2[i] = int(s[i]) } return LcpArrayIntSlice(s2, sa) } // MatchBySA finds all matches between a text and a pattern by using Suffix Array. // Time complexity: O(|P| * log|T|) func MatchBySA(text string, tsa []int, pattern string) (left, right int) { bs := func(initOK, initNG int, isOK func(mid int) bool) (ok int) { ng := initNG ok = initOK for int(math.Abs(float64(ok-ng))) > 1 { mid := (ok + ng) / 2 if isOK(mid) { ok = mid } else { ng = mid } } return ok } min := func(a, b int) int { if a < b { return a } return b } left = bs(len(tsa), -1, func(mid int) bool { L := tsa[mid] R := min(tsa[mid]+len(pattern), len(text)) substr := text[L:R] return pattern <= substr }) right = bs(-1, len(tsa), func(mid int) bool { L := tsa[mid] R := min(tsa[mid]+len(pattern), len(text)) substr := text[L:R] return pattern >= substr }) return } func SuffixArrayIntSlice(s []int) []int { n := len(s) idx := make([]int, n) for i := 0; i < n; i++ { idx[i] = i } sort.Slice(idx, func(l, r int) bool { return s[l] < s[r] }) s2 := make([]int, n) now := 0 for i := 0; i < n; i++ { if i != 0 && s[idx[i-1]] != s[idx[i]] { now++ } s2[idx[i]] = now } return _saIs(s2, now) } func SuffixArrayLimitedIntSlice(s []int, upper int) []int { sa := _saIs(s, upper) return sa } func LcpArrayIntSlice(s, 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 } j := sa[rnk[i]-1] for ; j+h < n && i+h < n; h++ { if s[j+h] != s[i+h] { break } } lcp[rnk[i]-1] = h } return lcp } func _saIs(s []int, upper int) []int { n := len(s) if n == 0 { return []int{} } if n == 1 { return []int{0} } if n == 2 { if s[0] < s[1] { return []int{0, 1} } else { return []int{1, 0} } } sa := make([]int, n) ls := make([]bool, n) for i := n - 2; i >= 0; i-- { if s[i] == s[i+1] { ls[i] = ls[i+1] } else { ls[i] = s[i] < s[i+1] } } sumL, sumS := make([]int, upper+1), make([]int, upper+1) for i := 0; i < n; i++ { if !ls[i] { sumS[s[i]]++ } else { sumL[s[i]+1]++ } } for i := 0; i <= upper; i++ { sumS[i] += sumL[i] if i < upper { sumL[i+1] += sumS[i] } } induce := func(lms []int) { for i := 0; i < n; i++ { sa[i] = -1 } buf := make([]int, upper+1) copy(buf, sumS) for _, d := range lms { if d == n { continue } sa[buf[s[d]]] = d buf[s[d]]++ } copy(buf, sumL) sa[buf[s[n-1]]] = n - 1 buf[s[n-1]]++ for i := 0; i < n; i++ { v := sa[i] if v >= 1 && !ls[v-1] { sa[buf[s[v-1]]] = v - 1 buf[s[v-1]]++ } } copy(buf, sumL) for i := n - 1; i >= 0; i-- { v := sa[i] if v >= 1 && ls[v-1] { buf[s[v-1]+1]-- sa[buf[s[v-1]+1]] = v - 1 } } } lmsMap := make([]int, n+1) for i, _ := range lmsMap { lmsMap[i] = -1 } m := 0 for i := 1; i < n; i++ { if !ls[i-1] && ls[i] { lmsMap[i] = m m++ } } lms := make([]int, 0, m) for i := 1; i < n; i++ { if !ls[i-1] && ls[i] { lms = append(lms, i) } } induce(lms) if m != 0 { sortedLms := make([]int, 0, m) for _, v := range sa { if lmsMap[v] != -1 { sortedLms = append(sortedLms, v) } } recS := make([]int, m) recUpper := 0 recS[lmsMap[sortedLms[0]]] = 0 for i := 1; i < m; i++ { l := sortedLms[i-1] r := sortedLms[i] endL, endR := n, n if lmsMap[l]+1 < m { endL = lms[lmsMap[l]+1] } if lmsMap[r]+1 < m { endR = lms[lmsMap[r]+1] } same := true if endL-l != endR-r { same = false } else { for l < endL { if s[l] != s[r] { break } l++ r++ } if l == n || s[l] != s[r] { same = false } } if !same { recUpper++ } recS[lmsMap[sortedLms[i]]] = recUpper } recSa := _saIs(recS, recUpper) for i := 0; i < m; i++ { sortedLms[i] = lms[recSa[i]] } induce(sortedLms) } return sa } /*******************************************************************/ /********** common constants **********/ const ( MOD = 1000000000 + 7 // MOD = 998244353 ALPH_N = 26 INF_I64 = math.MaxInt64 INF_B60 = 1 << 60 INF_I32 = math.MaxInt32 INF_B30 = 1 << 30 NIL = -1 EPS = 1e-10 ) /********** bufio setting **********/ func init() { // bufio.ScanWords <---> bufio.ScanLines reads = newReadString(os.Stdin, bufio.ScanWords) stdout = bufio.NewWriter(os.Stdout) } // mod can calculate a right residual whether value is positive or negative. func mod(val, m int) int { res := val % m if res < 0 { res += m } return res } // min returns the min integer among input set. // This function needs at least 1 argument (no argument causes panic). func min(integers ...int) int { m := integers[0] for i, integer := range integers { if i == 0 { continue } if m > integer { m = integer } } return m } // max returns the max integer among input set. // This function needs at least 1 argument (no argument causes panic). func max(integers ...int) int { m := integers[0] for i, integer := range integers { if i == 0 { continue } if m < integer { m = integer } } return m } // chmin accepts a pointer of integer and a target value. // If target value is SMALLER than the first argument, // then the first argument will be updated by the second argument. func chmin(updatedValue *int, target int) bool { if *updatedValue > target { *updatedValue = target return true } return false } // chmax accepts a pointer of integer and a target value. // If target value is LARGER than the first argument, // then the first argument will be updated by the second argument. func chmax(updatedValue *int, target int) bool { if *updatedValue < target { *updatedValue = target return true } return false } // sum returns multiple integers sum. func sum(integers ...int) int { var s int s = 0 for _, i := range integers { s += i } return s } /********** FAU standard libraries **********/ //fmt.Sprintf("%b\n", 255) // binary expression /********** I/O usage **********/ //str := reads() //i := readi() //X := readis(n) //S := readrs() //a := readf() //A := readfs(n) //str := ZeroPaddingRuneSlice(num, 32) //str := PrintIntsLine(X...) /*********** Input ***********/ var ( // reads returns a WORD string. reads func() string stdout *bufio.Writer ) func newReadString(ior io.Reader, sf bufio.SplitFunc) func() string { r := bufio.NewScanner(ior) r.Buffer(make([]byte, 1024), int(1e+9)) // for Codeforces r.Split(sf) return func() string { if !r.Scan() { panic("Scan failed") } return r.Text() } } // readi returns an integer. func readi() int { return int(_readInt64()) } func readi2() (int, int) { return int(_readInt64()), int(_readInt64()) } func readi3() (int, int, int) { return int(_readInt64()), int(_readInt64()), int(_readInt64()) } func readi4() (int, int, int, int) { return int(_readInt64()), int(_readInt64()), int(_readInt64()), int(_readInt64()) } // readll returns as integer as int64. func readll() int64 { return _readInt64() } func readll2() (int64, int64) { return _readInt64(), _readInt64() } func readll3() (int64, int64, int64) { return _readInt64(), _readInt64(), _readInt64() } func readll4() (int64, int64, int64, int64) { return _readInt64(), _readInt64(), _readInt64(), _readInt64() } func _readInt64() int64 { i, err := strconv.ParseInt(reads(), 0, 64) if err != nil { panic(err.Error()) } return i } // readis returns an integer slice that has n integers. func readis(n int) []int { b := make([]int, n) for i := 0; i < n; i++ { b[i] = readi() } return b } // readlls returns as int64 slice that has n integers. func readlls(n int) []int64 { b := make([]int64, n) for i := 0; i < n; i++ { b[i] = readll() } return b } // readf returns an float64. func readf() float64 { return float64(_readFloat64()) } func _readFloat64() float64 { f, err := strconv.ParseFloat(reads(), 64) if err != nil { panic(err.Error()) } return f } // ReadFloatSlice returns an float64 slice that has n float64. func readfs(n int) []float64 { b := make([]float64, n) for i := 0; i < n; i++ { b[i] = readf() } return b } // readrs returns a rune slice. func readrs() []rune { return []rune(reads()) } /*********** Output ***********/ // PrintIntsLine returns integers string delimited by a space. func PrintIntsLine(A ...int) string { res := []rune{} for i := 0; i < len(A); i++ { str := strconv.Itoa(A[i]) res = append(res, []rune(str)...) if i != len(A)-1 { res = append(res, ' ') } } return string(res) } // PrintIntsLine returns integers string delimited by a space. func PrintInts64Line(A ...int64) string { res := []rune{} for i := 0; i < len(A); i++ { str := strconv.FormatInt(A[i], 10) // 64bit int version res = append(res, []rune(str)...) if i != len(A)-1 { res = append(res, ' ') } } return string(res) } // Printf is function for output strings to buffered os.Stdout. // You may have to call stdout.Flush() finally. func printf(format string, a ...interface{}) { fmt.Fprintf(stdout, format, a...) } /*********** Debugging ***********/ // debugf is wrapper of fmt.Fprintf(os.Stderr, format, a...) func debugf(format string, a ...interface{}) { fmt.Fprintf(os.Stderr, format, a...) } // ZeroPaddingRuneSlice returns binary expressions of integer n with zero padding. // For debugging use. func ZeroPaddingRuneSlice(n, digitsNum int) []rune { sn := fmt.Sprintf("%b", n) residualLength := digitsNum - len(sn) if residualLength <= 0 { return []rune(sn) } zeros := make([]rune, residualLength) for i := 0; i < len(zeros); i++ { zeros[i] = '0' } res := []rune{} res = append(res, zeros...) res = append(res, []rune(sn)...) return res }