#include "bits/stdc++.h" #include #include using namespace std; #define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++) #define rep(i,n) repl(i,0,n) #define replrev(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--) #define reprev(i,n) replrev(i,0,n) #define repi(itr,ds) for(auto itr=ds.begin();itr!=ds.end();itr++) #define all(a) a.begin(),a.end() #define mp make_pair #define mt make_tuple #define INF 2000000000 #define INFL 1000000000000000000LL #define EPS (1e-10) #define MOD 1000000007 #define PI 3.1415926536 #define RMAX 4294967295 typedef long long ll; typedef pair P; typedef vector vi; typedef vector vll; typedef vector vb; typedef vector vc; typedef vector vs; typedef vector vd; typedef vector

vP; typedef vector > vvi; typedef vector > vvb; typedef vector > vvll; typedef vector > vvc; typedef vector > vvs; typedef vector > vvd; typedef vector > vvP; typedef priority_queue, greater > pqli; typedef priority_queue, greater > pqlll; typedef priority_queue, greater

> pqlP; /* // シンプルな構文解析用 typedef string::const_iterator State; class ParseError {}; //*/ struct Edge { int from, to, cost; bool operator<(Edge e) { return cost < e.cost; } }; typedef vector Edges; typedef vector Graph; vector makeTableKMP(const string &str){ vector border(str.size() + 1); border[0] = -1; int j = -1; for (int i = 0; i < str.size(); i++) { while (j >= 0 && str[i] != str[j]) j = border[j]; j++; //border[i+1] = j; if (str[i+1] == str[j]) border[i+1] = border[j]; else border[i+1] = j; } return border; } vector searchKMP(const string& str, const string& word) { vector table = makeTableKMP(word), ret; int m = 0, i = 0, n = str.size(); /* while (m + i < n) { cout< 0) i = table[i]; } } */ int j; i= j = 0; while (j < n) { while (i > -1 && word[i] != str[j]) i = table[i]; i++; j++; if (i >= word.size()) { ret.push_back(j - i); i = table[i]; } } return ret; } int main(void) { cin.tie(0); ios::sync_with_stdio(false); string S; int M; cin >> S >> M; ll ans = 0; rep(i, M){ string word; cin >> word; ans += searchKMP(S, word).size(); } cout << ans << endl; return 0; }