#include #include #include using namespace std; using namespace atcoder; using ll = long long; using ull = unsigned long long; using ld = long double; using vi = vector; using vvi = vector; using vvvi = vector; using vl = vector; using vvl = vector; using vll = vector; using vvll = vector; using vvvll = vector; using vb = vector; using vvb = vector; using pii = pair; using pll = pair; using vpii = vector; using vpll = vector; using vstr = vector; constexpr ll INF_LL=1e17; constexpr int INF_I=1LL<<30; constexpr ll inf = 1e12 + 7; #define rep(i,n) for(int i=0; i<((int)(n)); i++) #define reps(i,n) for(int i=1; i<=((int)(n)); i++) #define vector_cin(x) for(auto &n : (x)) cin >> n #define ALL(x) (x).begin(), (x).end() #define YesNo(x) ((x) ? "Yes": "No") #define pb emplace_back #define to_lower(S) transform(ALL((S)), (S).begin(), ::tolower) #define to_upper(S) transform(ALL((S)), (S).begin(), ::toupper) #define mp make_pair #define mt make_tuple template bool chmax(T &a, const T& b) {if (a < b){a = b;return true;}return false;} template bool chmin(T &a, const T& b) {if (a > b){a = b;return true;}return false;} ll ceilint(ll x, ll y) {return (x + y - 1) / y;} void Main(); int main() {std::cin.tie(nullptr);std::ios_base::sync_with_stdio(false);std::cout << std::fixed << std::setprecision(15);Main();return 0;} template ostream &operator<<(ostream &os, const pair &p) { os << "(" << p.first << "," << p.second << ")"; return os; } template istream &operator>>(istream &is, pair &p) { is >> p.first >> p.second; return is; } template ostream &operator<<(ostream &os, const vector &v) { for (int i = 0; i < (int)v.size(); i++) { os << v[i] << (i + 1 != (int)v.size() ? " ": "");}return os;} template ostream &operator<<(ostream &os, const vector> &v) { for (int i = 0; i < (int)v.size(); i++) { os << v[i] << endl;} return os;} template ostream &operator<<(ostream &os, const vector>> &v) { for (int i = 0; i < (int)v.size(); i++) { os << "i = " << i << endl; os << v[i];}return os;} template istream &operator>>(istream &is, vector &v) { for (T &in : v) is >> in; return is; } template ostream &operator<<(ostream &os, const map &mp) { for (auto &[key, val] : mp) { os << key << ":" << val << " ";} return os;} template ostream &operator<<(ostream &os, const set &st) { auto itr = st.begin(); for (int i = 0; i < (int)st.size(); i++) {os << *itr << (i + 1 != (int)st.size() ? " ": "");itr++;}return os;} template ostream &operator<<(ostream &os, const multiset &st){ auto itr = st.begin(); for (int i = 0; i < (int)st.size(); i++) { os << *itr << (i + 1 != (int)st.size() ? " ": "");itr++;}return os;} template ostream &operator<<(ostream &os, queue q){ while (q.size()) { os << q.front() << " ";q.pop(); }return os;} template ostream &operator<<(ostream &os, deque q) { while (q.size()) { os << q.front() << " "; q.pop_front();} return os;} template ostream &operator<<(ostream &os, stack st) { while (st.size()){ os << st.top() << " "; st.pop();} return os;} template ostream &operator<<(ostream &os, priority_queue pq) { while (pq.size()) {os << pq.top() << " ";pq.pop();}return os;} //-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- template< unsigned mod > struct RollingHash {vector< unsigned > hashed, power;inline unsigned mul(unsigned a, unsigned b) const {unsigned long long x = (unsigned long long) a * b;unsigned xh = (unsigned) (x >> 32), xl = (unsigned) x, d, m;asm("divl %4; \n\t": "=a" (d),"=d" (m) : "d" (xh),"a" (xl),"r" (mod));return m;} RollingHash(const string &s, unsigned base = 10007) { int sz = (int) s.size(); hashed.assign(sz + 1, 0); power.assign(sz + 1, 0); power[0] = 1; for(int i = 0; i < sz; i++) { power[i + 1] = mul(power[i], base); hashed[i + 1] = mul(hashed[i], base) + s[i]; if(hashed[i + 1] >= mod) hashed[i + 1] -= mod; } } unsigned get(int l, int r) const { unsigned ret = hashed[r] + mod - mul(hashed[l], power[r - l]); if(ret >= mod) ret -= mod; return ret; } unsigned connect(unsigned h1, int h2, int h2len) const { unsigned ret = mul(h1, power[h2len]) + h2; if(ret >= mod) ret -= mod; return ret; } int LCP(const RollingHash< mod > &b, int l1, int r1, int l2, int r2) { int len = min(r1 - l1, r2 - l2); int low = -1, high = len + 1; while(high - low > 1) { int mid = (low + high) / 2; if(get(l1, l1 + mid) == b.get(l2, l2 + mid)) low = mid; else high = mid; } return (low); } }; using RH = RollingHash< 1000000007 >; void Main () { string S; cin >> S; ll M; cin >> M; ll ans = 0; rep(i, M) { string C; cin >> C; string T = S + C; RH rh(T); rep(i, S.size() - C.size() + 1) { if (rh.get(i, i + C.size()) == rh.get(S.size(), S.size() + C.size())) ans++; } } cout << ans << endl; }