#include #include #include using namespace std; using namespace atcoder; using ll = long long; using mint = modint998244353; //using mint = modint1000000007; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define repu(i, s, t) for (int i = (int)(s); i < (int)(t); i++) #define repd(i, s, t) for (int i = (int)(s)-1; i >= (int)(t); i--) #define all(v) v.begin(), v.end() template bool chmax(T &a, const T b) { if(a >= b) return false; a = b; return true; } template bool chmin(T &a, const T b) { if(a <= b) return false; a = b; return true; } template istream& operator>>(istream &in, vector &a) { for(T &x: a) in >> x; return in; } template ostream& operator<<(ostream &out, const vector &a) { for(const T &x: a) out << x << ' '; return out; } const int di[] = {1, 0, -1, 0, 1, 1, -1, -1, 0}; const int dj[] = {0, 1, 0, -1, -1, 1, 1, -1, 0}; struct KMP { int n; string s; vector skip; KMP(string s_) : n(s_.size()), s(s_), skip(int(s_.size())+1) { assert(n > 0); skip[0] = skip[1] = 0; int cur = 0; for(int i = 1; i < n; i++) { while(cur > 0 && s[i] != s[cur]) cur = skip[cur]; if(s[i] == s[cur]) cur++; skip[i+1] = cur; } } int match(string &t, int ti=0, int cur=0) { for(int i = ti; i < int(t.size()); i++) { while(cur > 0 && s[cur] != t[i]) cur = skip[cur]; if(s[cur] == t[i]) cur++; if(cur == n) return i-n+1; } return -1; } vector all_match(string &t) { int ti; if((ti = match(t, 0, 0)) < 0) return {}; vector res(1, ti); ti+=n; while((ti = match(t, ti, skip.back())) >= 0) { res.push_back(ti); ti+=n; } return res; } }; int main() { string s; int m; cin >> s >> m; vector c(m); cin >> c; int ans = 0; rep(i, m) { KMP ref(c[i]); ans += ref.all_match(s).size(); } cout << ans << endl; return 0; }