/* #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") //*/ #include // #include using namespace std; // using namespace atcoder; #define DEBUG(x) cerr<<#x<<": "< #define vl vector #define vii vector< vector > #define vll vector< vector > #define vs vector #define pii pair #define pis pair #define psi pair #define pll pair template pair operator+(const pair &s, const pair &t) { return pair(s.first + t.first, s.second + t.second); } template pair operator-(const pair &s, const pair &t) { return pair(s.first - t.first, s.second - t.second); } template ostream& operator<<(ostream& os, pair p) { os << "(" << p.first << ", " << p.second << ")"; return os; } #define X first #define Y second #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep1(i,n) for(int i=1;i<=(int)(n);i++) #define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--) #define rrep1(i,n) for(int i=(int)(n);i>0;i--) #define REP(i,a,b) for(int i=a;i bool chmax(T &a, const T &b) { if (a bool chmin(T &a, const T &b) { if (a>b) { a = b; return 1; } return 0; } #define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end()); const ll inf = 1000000001; const ll INF = (ll)1e18 + 1; const long double pi = 3.1415926535897932384626433832795028841971L; int popcount(ll t) { return __builtin_popcountll(t); } // int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1}; // int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 }; vi dx = {0, 1, 0, -1}, dy = {-1, 0, 1, 0}; // vi dx2 = { 1,1,0,-1,-1,-1,0,1 }, dy2 = { 0,1,1,1,0,-1,-1,-1 }; struct Setup_io { Setup_io() { ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); cout << fixed << setprecision(25); } } setup_io; // const ll MOD = 1000000007; const ll MOD = 998244353; // #define mp make_pair //#define endl '\n' struct dice { mt19937 mt; dice() : mt(chrono::steady_clock::now().time_since_epoch().count()) {} // [0, x)の一様乱数 ll operator()(ll x) { return this->operator()(0, x); } // [x, y)の一様乱数 ll operator()(ll x, ll y) { uniform_int_distribution dist(x, y - 1); return dist(mt); } vl operator()(int n, ll x, ll y) { vl res(n); for (int i = 0; i < n; i++) res[i] = this->operator()(x, y); return res; } } rnd; template struct TrieNode { // 持たせたい好きな状態を持たせよう // 持たせたい好きな状態を持たせよう int next_idx[char_size]; // Trie木上での次の状態のインデックス,存在しない時は-1 vector exist_char; // 続きのノードが存在する文字 vector state_idx; // ちょうどこのノードと同じ文字列のインデックス(同じ文字列が複数回追加される時もあるので) int sub_num = 0; // このノード以下に存在する追加された文字列の数(!= ノードの数) TrieNode() { for (int i = 0; i < char_size; i++) next_idx[i] = -1; } }; template struct Trie { using Node = TrieNode; vector nodes; int str_num=0; // 追加された文字列の数(!= ノードの数) vector strs; // 追加された文字列とそのidの対応表,idが連番じゃない時はunordered_mapに変えて頑張って Trie() { nodes.push_back(Node()); } void add(string& s, int str_idx, int node_idx, int id) { // sと完全に一致するノード if (str_idx == s.size()) { nodes[node_idx].state_idx.push_back(id); nodes[node_idx].sub_num++; return; } // sの次の文字に対応するノードがまだない if (nodes[node_idx].next_idx[s[str_idx] - initial_char] == -1) { nodes[node_idx].next_idx[s[str_idx] - initial_char] = nodes.size(); nodes[node_idx].exist_char.push_back(s[str_idx] - initial_char); nodes.push_back(Node()); } add(s, str_idx+1, nodes[node_idx].next_idx[s[str_idx] - initial_char], id); nodes[node_idx].sub_num++; } void add(string& s, int id=-1) { if (id == -1) id = str_num; add(s, 0, 0, id); str_num++; strs.push_back(s); } // MLE注意かも int sub(string& s, int str_idx, int node_idx) { // sと完全に一致するノード if (str_idx == s.size()) { assert(nodes[node_idx].state_idx.size() > 0); // 適当に最後に突っ込まれたidを削除している int id = nodes[node_idx].state_idx.back(); nodes[node_idx].state_idx.pop_back(); nodes[node_idx].sub_num--; return id; } int next_node_idx = nodes[node_idx].next_idx[s[str_idx] - initial_char]; int id = sub(s, str_idx+1, next_node_idx); nodes[node_idx].sub_num--; assert(nodes[node_idx].sub_num >= 0); // sの次の文字に対応するノードは消えたが,このノードは消えないとき(このノードが根 or 他にも子がいる) if (nodes[next_node_idx].sub_num == 0 and (nodes[node_idx].sub_num > 0 or node_idx == 0)) { nodes[node_idx].next_idx[s[str_idx] - initial_char] = -1; rep (i, nodes[node_idx].exist_char.size()) { if (nodes[node_idx].exist_char[i] == s[str_idx] - initial_char) { nodes[node_idx].exist_char.erase(nodes[node_idx].exist_char.begin() + i); break; } } } return id; } // 削除した文字列のidを返す int sub(string& s) { int id = sub(s, 0, 0); str_num--; strs[id].clear(); strs[id].shrink_to_fit(); return id; } void query(string& s, int str_idx, int node_idx) { for (int id: nodes[node_idx].state_idx) { // s[0, str_idx)にちょうど一致する追加された文字列たちに対する処理 } if (str_idx == s.size()) { // ちょうどsと一致するノードが見つかったよ! return; } if (nodes[node_idx].next_idx[s[str_idx] - initial_char] == -1) { // これ以上sのprefixに共通するノードはない return; } return query(s, str_idx + 1, nodes[node_idx].next_idx[s[str_idx] - initial_char]); } // sのprefixに対する何らかの処理をしたい時 void query(string s) { query(s, 0, 0); } void dfs(int node_idx, int depth) { // 今の頂点に関する何らかの処理 // 今の頂点に関する何らかの処理(終わり) for (int c: nodes[node_idx].exist_char) { assert(nodes[node_idx].next_idx[c] != -1); dfs(nodes[node_idx].next_idx[c], depth + 1); } } // 根からdfsしたい時 void dfs() { dfs(0, 0); } string xor_min(string& s, int str_idx, int node_idx, string& t) { if (str_idx == s.size()) { // ちょうどsと一致するノードが見つかったよ! return t; } if (nodes[node_idx].next_idx[s[str_idx] - initial_char] != -1) { t += s[str_idx]; return xor_min(s, str_idx + 1, nodes[node_idx].next_idx[s[str_idx] - initial_char], t); } else { char c = '0' + ('1' - s[str_idx]); t += c; return xor_min(s, str_idx + 1, nodes[node_idx].next_idx[c - initial_char], t); } } // sとxorした時に最も小さくなる文字列を探索 string xor_min(string& s) { assert(initial_char == '0' and char_size == 2); assert(str_num > 0); string res; return xor_min(s, 0, 0, res); } }; template< int char_size, int initial_char > struct AhoCorasick : Trie< char_size + 1, initial_char > { const int FAIL = char_size; // next_idx で失敗した時の行き先をたどるための文字、最長の共通接尾辞の頂点に行く(なければ根) vector suf_cnt; // 現在のノードのsuffixに含まれる辞書に含まれる文字列の総和 bool is_built = false; // node_idxの状態に文字cが追加された際に訪れるノード int move(int node_idx, int c) { return this->nodes[node_idx].next_idx[c - initial_char]; } void build() { is_built = true; suf_cnt.resize(this->nodes.size()); // 自分そのものの数 for (int i = 0; i < this->nodes.size(); i++) { suf_cnt[i] = this->nodes[i].state_idx.size(); } // 根ルートと長さ一の文字列は別に処理 queue qu; for (int i = 0; i <= char_size; i++) { if (this->nodes[0].next_idx[i] == -1) { this->nodes[0].next_idx[i] = 0; } else { int next_node = this->nodes[0].next_idx[i]; this->nodes[next_node].next_idx[FAIL] = 0; qu.push(next_node); } } while (qu.size()) { int node_idx = qu.front(); qu.pop(); int fail_idx = this->nodes[node_idx].next_idx[FAIL]; suf_cnt[node_idx] += suf_cnt[fail_idx]; // 頭をとった接尾辞の分を足す for (int c = 0; c < char_size; c++) { if (this->nodes[node_idx].next_idx[c] == -1) { this->nodes[node_idx].next_idx[c] = move(fail_idx, c + initial_char); continue; } int next_node = this->nodes[node_idx].next_idx[c]; this->nodes[next_node].next_idx[FAIL] = this->nodes[fail_idx].next_idx[c]; qu.push(next_node); } } } ll match(string s) { assert(is_built); ll res = 0; int node_idx = 0; for (int i = 0; i < s.size(); i++) { node_idx = move(node_idx, s[i]); res += suf_cnt[node_idx]; } return res; } }; signed main() { string s; cin >> s; AhoCorasick<26, 'A'> aho; int m; cin >> m; rep (i, m) { string t; cin >> t; aho.add(t); } aho.build(); cout << aho.match(s) << endl; }