#include #include #include #include #include #include #include #include #include #include #include #include #include static const int MOD = 1000000007; using ll = long long; using u32 = unsigned; using u64 = unsigned long long; using namespace std; template constexpr T INF = ::numeric_limits::max()/32*15+208; template class AhoCorasick { public: struct Node { array to; int fail; int val; }; explicit AhoCorasick() : v(1) {} vector v; vector ord; int add(string &s, int x = 0, int cur = 0){ for (auto &&i : s) { if(!v[cur].to[i-start]) v[cur].to[i-start] = v.size(), v.emplace_back(); cur = v[cur].to[i-start]; } return cur; } void build() { v[0].fail = -1; int l = 0, r = 1; ord.clear(); ord.reserve(v.size()); ord.emplace_back(0); while(l < r){ int i = ord[l]; l++; for (int c = 0; c < W; ++c) { if(!v[i].to[c]) continue; int to = v[i].to[c]; v[to].fail = (v[i].fail == -1 ? 0 : v[v[i].fail].to[c]); ord.emplace_back(to); r++; } if(i != 0){ for (int c = 0; c < W; ++c) { if(!v[i].to[c]) v[i].to[c] = v[v[i].fail].to[c]; } } } } inline int next(int x, char c){ return v[x].to[c-start]; } }; int main() { // ios_base::sync_with_stdio(false); // cin.tie(nullptr); AhoCorasick<26, 'A'> aho; string s; cin >> s; int m; cin >> m; vector ids(m); vector x(m); for (int i = 0; i < m; ++i) { string t; cin >> t; x[i] = t; ids[i] = aho.add(t); } aho.build(); vector dp(aho.v.size()); for (int i = 0; i < m; ++i) { dp[ids[i]]++; } for (auto &&i : aho.ord) { if(i) dp[i] += dp[aho.v[i].fail]; } int cur = 0, ans = 0; for (auto &&i : s) { cur = aho.next(cur, i); ans += dp[cur]; } cout << ans << "\n"; return 0; }