/* -*- coding: utf-8 -*- * * 430.cc: No.430 文字列検索 - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ /* typedef */ typedef vector vi; typedef unsigned char uchar; typedef vector vuc; // global variables // subroutines inline uchar mask(int i) { return (uchar)(1 << (7 - i)); } inline bool tget(vuc &t, int i) { return (t[i / 8] & mask(i % 8)) ? true : false; } inline void tset(vuc &t, int i, bool b) { if (b) t[i / 8] |= mask(i % 8); else t[i / 8] &= ~mask(i % 8); } inline bool isLMS(vuc &t, int i) { return (i > 0 && tget(t, i) && ! tget(t, i - 1)); } // find the start or end of each bucket void getBuckets(int *s, vi &bkt, int n, int k, bool end) { // clear all buckets bkt.assign(k, 0); // compute the size of each bucket for (int i = 0; i < n; i++) bkt[s[i]]++; for (int i = 0, sum = 0; i < k; i++) { sum += bkt[i]; bkt[i] = end ? sum : sum - bkt[i]; } } // compute SAl void induceSAl(vuc &t, int *SA, int *s, vi &bkt, int n, int k, bool end) { // find starts of buckets getBuckets(s, bkt, n, k, end); for (int i = 0; i < n; i++) { int j = SA[i] - 1; if (j >= 0 && ! tget(t, j)) SA[bkt[s[j]]++] = j; } } // compute SAs void induceSAs(vuc &t, int *SA, int *s, vi &bkt, int n, int k, bool end) { // find ends of buckets getBuckets(s, bkt, n, k, end); for (int i = n - 1; i >= 0; i--) { int j = SA[i] - 1; if (j >= 0 && tget(t, j)) SA[--bkt[s[j]]] = j; } } // find the suffix array SA of s[0..n-1] in {1..K} // require s[n-1]=0 (the sentinel!), n>=2 // use a working space (excluding s and SA) of // at most 2.25n+O(1) for a constant alphabet void SA_IS(int *s, int *SA, int n, int k) { // LS-type array in bits vuc t(n / 8 + 1); // classify the type of each character // the sentinel must be in s1, important!!! tset(t, n - 1, true); tset(t, n - 2, false); for (int i = n - 3; i >= 0; i--) if (s[i] < s[i + 1] || (s[i] == s[i + 1] && tget(t, i + 1))) tset(t, i, true); // stage 1: reduce the problem by at least 1/2 // sort all the S-substrings // bucket array vi bkt(k); // find ends of buckets getBuckets(s, bkt, n, k, true); for (int i = 0; i < n; i++) SA[i] = -1; for (int i = 1; i < n; i++) if (isLMS(t, i)) SA[--bkt[s[i]]] = i; induceSAl(t, SA, s, bkt, n, k, false); induceSAs(t, SA, s, bkt, n, k, true); // compact all the sorted substrings into // the first n1 items of SA // 2*n1 must be not larger than n (proveable) int n1 = 0; for (int i = 0; i < n; i++) if (isLMS(t, SA[i])) SA[n1++] = SA[i]; // find the lexicographic names of substrings // init the name array buffer for (int i = n1; i < n; i++) SA[i] = -1; int name = 0, prev = -1; for (int i = 0; i < n1; i++) { int pos = SA[i]; bool diff = false; for (int d = 0; d < n; d++) { if (prev == -1 || s[pos + d] != s[prev + d] || tget(t, pos + d) != tget(t, prev + d)) { diff = true; break; } else if (d > 0 && (isLMS(t, pos + d) || isLMS(t, prev + d))) break; } if (diff) name++, prev = pos; pos /= 2; SA[n1 + pos] = name - 1; } for (int i = n - 1, j = n - 1; i >= n1; i--) if (SA[i] >= 0) SA[j--] = SA[i]; // stage 2: solve the reduced problem // recurse if names are not yet unique int *SA1 = SA, *s1 = SA + n - n1; if (name < n1) SA_IS(s1, SA1, n1, name); else // generate the suffix array of s1 directly for (int i = 0; i < n1; i++) SA1[s1[i]] = i; // stage 3: induce the result for // the original problem // bucket array bkt.assign(k, 0); // put all the LMS characters into their buckets // find ends of buckets getBuckets(s, bkt, n, k, true); for (int i = 1, j = 0; i < n; i++) if (isLMS(t, i)) s1[j++] = i; // get p1 // get index in s for (int i = 0; i < n1; i++) SA1[i] = s1[SA1[i]]; // init SA[n1..n-1] for (int i = n1; i < n; i++) SA[i] = -1; for (int i = n1 - 1; i >= 0; i--) { int j=SA[i]; SA[i] = -1; SA[--bkt[s[j]]] = j; } induceSAl(t, SA, s, bkt, n, k, false); induceSAs(t, SA, s, bkt, n, k, true); } void SA_IS(string &s, vi &SA, int k = 256) { int n = s.size(); int *buf0 = new int[n + 1], *buf1 = new int[n + 1]; for (int i = 0; i < n; i++) buf0[i] = s[i]; buf0[n] = 0; SA_IS(buf0, buf1, n + 1, k); SA.resize(n + 1); for (int i = 0; i <= n; i++) SA[i] = buf1[i]; } void LCP(string &s, vi &sa, vi &lcp) { int n = s.size(); lcp.resize(n + 1); vi rank_(n + 1); for (int i = 0; i <= n; i++) rank_[sa[i]] = i; int h = 0; lcp[0] = 0; for (int i = 0; i < n; i++) { int j = sa[rank_[i] - 1]; if (h > 0) h--; for (; j + h < n && i + h < n; h++) if (s[j + h] != s[i + h]) break; lcp[rank_[i]] = h; } } bool lt_substr(string &s, string &t, int si = 0, int ti = 0) { int sn = s.size(), tn = t.size(); while (si < sn && ti < tn) { if (s[si] < t[ti]) return true; if (s[si] > t[ti]) return false; si++, ti++; } return (si >= sn && ti < tn); } int sa_lb(string &s, vi &SA, string &t) { int i0 = -1; int i1 = SA.size(); while (i0 + 1 < i1) { int im = (i0 + i1) / 2; if (lt_substr(s, t, SA[im])) i0 = im; else i1 = im; } return i1; } /* main */ int main() { string s; cin >> s; vi SA, lcp; SA_IS(s, SA); LCP(s, SA, lcp); //for (int i = 0; i < SA.size(); i++) printf("%d %d\n", SA[i], lcp[i]); int m; cin >> m; int sum = 0; while (m--) { string t; cin >> t; int i0 = sa_lb(s, SA, t); t.back()++; int i1 = sa_lb(s, SA, t); sum += i1 - i0; //printf("%d %d\n", i0, i1); } printf("%d\n", sum); return 0; }