#include #define REP(i,n) for (long long i=0;i<(n);i++) #define FOR(i,a,b) for (long long i=(a);i<(b);i++) #define RREP(i,n) for(long long i=n;i>=0;i--) #define RFOR(i,a,b) for(long long i=(a);i>(b);i--) #define dump1d_arr(array) REP(i,array.size()) cerr << #array << "[" << (i) << "] ==> " << (array[i]) << endl #define dump2d_arr(array) REP(i,array.size()) REP(j,array[i].size()) cerr << #array << "[" << (i) << "]" << "[" << (j) << "] ==> " << (array[i][j]) << endl #define dump(x) cerr << #x << " => " << (x) << endl #define dumpP(p) cerr << "( " << p.first << " , " << p.second << " )" << ends #define SORT(c) sort((c).begin(),(c).end()) #define MIN(vec) *min_element(vec.begin(), vec.end()) #define MAX(vec) *max_element(vec.begin(), vec.end()) #define UNIQ(vec) vec.erase(unique(vec.begin(), vec.end()),vec.end()) //ソートの必要あり #define IN(n,m) (!(m.find(n) == m.end())) #define ENUM(m) for (auto itr = m.begin(); itr != m.end(); ++itr) #define dump_MAP(m) for(auto itr = m.begin(); itr != m.end(); ++itr) { cerr << itr->first << " --> " << itr->second << endl; } #define FINDL(vec,x) (lower_bound(vec.begin(),vec.end(),x) - vec.begin()) #define FINDU(vec,x) (upper_bound(vec.begin(),vec.end(),x) - vec.begin()) #define ROUND(N) setprecision(N) #define ROUND_PRINT(N,val) cout << fixed;cout << setprecision(N) << val << endl #define ALL(a) (a).begin(),(a).end() #define RALL(a) (a).rbegin(), (a).rend() #define INARR(h,w,x,y) (0 <= y && y < h && 0 <= x && x < w) #define EQ(a,b) (abs(a - b) < 1e-10) using namespace std; constexpr int dx[4] = {0,1,0,-1}; constexpr int dy[4] = {1,0,-1,0}; constexpr long double pi = M_PI; constexpr double EPS = 1e-10; constexpr long MOD = 1000000007; constexpr short shINF = 32767; constexpr long loINF = 2147483647; constexpr long long llINF = 9223372036854775807; typedef long long LL; typedef vector VI; typedef vector VVI; typedef vector VL; typedef vector VVL; typedef vector VS; typedef pair pr; typedef vector VB; typedef vector VP; typedef priority_queue,greater> pq; struct Trie { bool leaf; Trie* node[256]; Trie(){ leaf = false; for(int i=0; i<256; i++){ node[i] = (Trie*)0; } } void insert(const string &str){ Trie *r = this; for(int i=0; inode[c]) r->node[c] = new Trie; r = r->node[c]; } r->leaf = true; } int find(const string &str) const { const Trie *r = this; int cnt = 0; for(int i=0; inode[c]) return cnt; r = r->node[c]; if ((r->leaf) == 1) { ++cnt; } } return cnt; } }; int main(void) { cin.tie(0); ios::sync_with_stdio(false); long M; string S,C; cin >> S >> M; Trie tree; REP(i,M) { cin >> C; tree.insert(C); } string s = S; LL cnt = 0; while (s.size() > 0) { cnt += tree.find(s); s = s.substr(1); } cout << cnt << endl; }