#include using namespace std; #define rep(i,n) for (int i = 0; i< (n); ++i) #define repi(i, a, b) for (int i = (a); i < (b); ++i) #define all(x) (x).begin(), (x).end() #define fore(i, a) for(auto &i:a) using ll = long long; using int64 = long long; #define DEBUG(x) cerr << #x << ": "; for (auto _ : x) cerr << _ << " "; cerr << endl; const int64 infll = (1LL << 62) - 1; const int inf = (1 << 30) - 1; struct IoSetup { IoSetup() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(10); cerr << fixed << setprecision(10); } } iosetup; 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 != v.size() ? " " : ""); } return os; } template istream& operator>>(istream& is, vector& v) { for (T& in : v) is >> in; return is; } template inline bool chmax(T1& a, T2 b) { return a < b && (a = b, true); } template inline bool chmin(T1& a, T2 b) { return a > b && (a = b, true); } template vector make_v(size_t a) { return vector(a); } template auto make_v(size_t a, Ts... ts) { return vector(ts...))>(a, make_v(ts...)); } template typename enable_if::value == 0>::type fill_v(T& t, const V& v) { t = v; } template typename enable_if::value != 0>::type fill_v(T& t, const V& v) { for (auto& e : t) fill_v(e, v); } template struct FixPoint : F { explicit FixPoint(F&& f) : F(std::forward(f)) {} template decltype(auto) operator()(Args&&... args) const { return F::operator()(*this, std::forward(args)...); } }; template inline decltype(auto) MFP(F&& f) { return FixPoint{std::forward(f)}; } struct Aho { using MP = map; vector to; vector cnt, fail, parent; vector> SU; ll idx; map str; Aho(): to(1), cnt(1), parent(1), idx(0){}; int add(const string& s) { int v = 0; for (char c : s) { if (!to[v].count(c)) { to[v][c] = to.size(); parent.push_back(v); to.push_back(MP()); cnt.push_back(0); } v = to[v][c]; } cnt[v]++; str[v] = idx++; return v; } void init() { fail = vector(to.size(), -1); SU = vector>(to.size()); queue q; q.push(0); while (!q.empty()) { int v = q.front(); q.pop(); if(str.count(v))SU[v].insert(str[v]); for (auto [c,u] : to[v]) { fail[u] = (*this)(fail[v],c); cnt[u] += cnt[fail[u]]; for(auto xx:SU[fail[u]]){ SU[u].insert(xx); } q.push(u); } } } int operator()(int v, char c) const { while (v != -1) { auto it = to[v].find(c); if (it != to[v].end()) return it->second; v = fail[v]; } return 0; } int operator[](int v) const { return cnt[v];} }; int main(){ string s; cin >> s; ll m; cin >> m; Aho aho; rep(i, m){ string c;cin >> c; aho.add(c); } aho.init(); ll cnt = 0; int v = 0; rep(i, s.size()){ v = aho(v,s[i]); cnt += aho[v]; } cout << cnt << "\n"; }