#include #define FOR(i,a,b) for(int i= (a); i<((int)b); ++i) #define RFOR(i,a) for(int i=(a); i >= 0; --i) #define FOE(i,a) for(auto i : a) #define ALL(c) (c).begin(), (c).end() #define RALL(c) (c).rbegin(), (c).rend() #define DUMP(x) cerr << #x << " = " << (x) << endl; #define SUM(x) std::accumulate(ALL(x), 0LL) #define MIN(v) *std::min_element(v.begin(), v.end()) #define MAX(v) *std::max_element(v.begin(), v.end()) #define EXIST(v,x) (std::find(v.begin(), v.end(), x) != v.end()) #define BIT(n) (1LL<<(n)) #define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end()); typedef long long LL; template using V = std::vector; template using VV = std::vector>; template using VVV = std::vector>>; template inline T ceil(T a, T b) { return (a + b - 1) / b; } template inline void print(T x) { std::cout << x << std::endl; } template inline void print_vec(const std::vector &v) { for (int i = 0; i < v.size(); ++i) { if (i != 0) {std::cout << " ";} std::cout << v[i];} std::cout << "\n"; } template inline bool inside(T y, T x, T H, T W) {return 0 <= y and y < H and 0 <= x and x < W; } template inline double euclidean_distance(T y1, T x1, T y2, T x2) { return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); } template inline double manhattan_distance(T y1, T x1, T y2, T x2) { return abs(x1 - x2) + abs(y1 - y2); } const int INF = 1L << 30; const double EPS = 1e-9; const std::string YES = "YES", Yes = "Yes", NO = "NO", No = "No"; const std::vector dy4 = { 0, 1, 0, -1 }, dx4 = { 1, 0, -1, 0 }; // 4近傍(右, 下, 左, 上) const std::vector dy8 = { 0, -1, 0, 1, 1, -1, -1, 1 }, dx8 = { 1, 0, -1, 0, 1, 1, -1, -1 }; class AhoCorasick { struct Node { std::unordered_map next; Node* failure; std::vector output; Node() { failure = nullptr; }; void insert(int i, const std::string &s) { if (i >= s.size()) { output.emplace_back(s); return; } if (this->next[s[i]] == nullptr) { this->next[s[i]] = new Node(); } this->next[s[i]]->insert(i + 1, s); } }; public: Node root; void insert(const std::string &word) { root.insert(0, word); } void build() { std::queue que; que.push(&root); while (not que.empty()) { auto node = que.front(); que.pop(); for (auto &p : node->next) { auto now = node; auto next = p.second; auto c = p.first; que.push(next); while (now != &root and now->failure->next[c] == nullptr) { now = now->failure; } if (now == &root) { next->failure = &root; continue; } next->failure = now->failure->next[c]; for (auto s : next->failure->output) { next->output.emplace_back(s); } } } } std::vector> find(const std::string &text) { std::vector> ans; auto now = &root; for (int i = 0; i < text.size(); ++i) { while (now != &root and now->next[text[i]] == nullptr) { now = now->failure; } if (now->next[text[i]] == nullptr) { continue; } now = now->next[text[i]]; for (int j = 0; j < now->output.size(); ++j) { ans.emplace_back(make_pair(i - now->output[j].size() + 1, now->output[j])); } } return ans; } }; using namespace std; int main() { cin.tie(0); ios::sync_with_stdio(false); string S; cin >> S; int M; cin >> M; AhoCorasick ac; FOR(i, 0, M) { string C; cin >> C; ac.insert(C); } ac.build(); print(ac.find(S).size()); return 0; }