#include #define ll long long #define INF 1000000005 #define MOD 1000000007 #define EPS 1e-10 #define rep(i,n) for(int i=0;i<(int)(n);++i) #define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i) #define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i) #define each(a,b) for(auto& (a): (b)) #define all(v) (v).begin(),(v).end() #define len(v) (int)(v).size() #define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end()) #define cmx(x,y) x=max(x,y) #define cmn(x,y) x=min(x,y) #define fi first #define se second #define pb push_back #define show(x) cout<<#x<<" = "<<(x)< P; typedef pair pll; typedef vector vi; typedef vector vvi; typedef vector vl; typedef vector vvl; typedef vector vd; typedef vector

vp; typedef vector vs; const int MAX_N = 100005; class AhoCorasick { private: using AC = AhoCorasick*; vector > ac; map next; AC t, fail, dnx; void add(const string& s, int pos, int id){ if(pos == (int)s.size()){ ac.emplace_back(id, pos); return; } if(!next[s[pos]]) next[s[pos]] = new AhoCorasick(); next[s[pos]]->add(s,pos+1,id); } AC count(vector >& res, int pos){ if(!fail) return this; for(auto val : ac) res[val.first].push_back(pos-val.second+1); if(dnx) dnx->count(res,pos); else dnx = fail->count(res,pos); return ac.size() ? this : dnx; } void match_(vector >& res, const string& s, int pos=0){ if(pos == (int)s.size()) return; if(next[s[pos]]){ next[s[pos]]->count(res, pos); next[s[pos]]->match_(res,s,pos+1); }else{ if(!fail) match_(res,s,pos+1); else fail->match_(res,s,pos); } } public: AhoCorasick() : fail(nullptr), dnx(nullptr){} //パターンを入力として木を構築 AhoCorasick(vector& pattern): AhoCorasick(){ int sz = (int)pattern.size(); t = new AhoCorasick(); for(int i = 0; i < sz; i++){ t->add(pattern[i],0,i); } queue que; que.push(t); t->fail = nullptr; while(!que.empty()){ AC nw = que.front(); que.pop(); for(auto p : nw->next){ int i = p.first; AC fail = nw->fail; while(fail && !fail->next.count(i)){ fail = fail->fail; } nw->next[i]->fail = (!fail ? t : fail->next[i]); que.push(nw->next[i]); } } } //sのインデックスpos(デフォルト0)以降に含まれる各パターンの開始位置をresで返す void match(vector >& res, const string& s, int pos=0){ t->match_(res,s,pos); } }; int main() { string s; cin >> s; int m; cin >> m; vector t(m); rep(i,m){ cin >> t[i]; } AhoCorasick ac(t); vvi ans(m); ac.match(ans,s); int sm = 0; rep(i, m){ sm += len(ans[i]); } cout << sm << "\n"; return 0; }