This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2873"
#include <iostream>
#include <string>
#include <vector>
#include "../../string/aho_corasick.hpp"
int main() {
std::string s;
int n;
std::cin >> s >> n;
ebi::aho_corasick<26, 'a'> ac;
for (int i = 0; i < n; i++) {
std::string p;
std::cin >> p;
ac.add(p);
}
ac.build();
int now = 0;
int ans = 0;
for (auto c : s) {
auto [x, y] = ac.move(c, now);
if (x > 0) {
ans++;
now = 0;
} else {
now = y;
}
}
std::cout << ans << '\n';
}
#line 1 "test/aoj/aoj_2873.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2873"
#include <iostream>
#include <string>
#include <vector>
#line 2 "string/aho_corasick.hpp"
#include <string.h>
#include <algorithm>
#include <cassert>
#include <map>
#include <queue>
#line 10 "string/aho_corasick.hpp"
#line 2 "string/trie.hpp"
#include <array>
#line 7 "string/trie.hpp"
namespace ebi {
template <int char_size, int margin> struct trie {
private:
struct trie_node {
int common;
std::array<int, char_size> nxt;
std::vector<int> accept;
trie_node() : common(0) {
nxt.fill(-1);
}
};
public:
trie() {
nodes.emplace_back(trie_node());
}
void add(const std::string &str) {
int idx = 0;
for (const auto &c : str) {
int val = c - margin;
assert(0 <= val && val < char_size);
if (nodes[idx].nxt[val] < 0) {
nodes[idx].nxt[val] = int(nodes.size());
nodes.emplace_back(trie_node());
}
idx = nodes[idx].nxt[val];
nodes[idx].common++;
}
nodes[idx].accept.emplace_back(nodes[0].common++);
}
template <class F>
void query(const std::string &str, int start, F func) const {
int idx = 0;
for (int i = start; i < int(str.size()); ++i) {
int val = str[i] - margin;
assert(0 <= val && val < char_size);
int nxt = nodes[idx].nxt[val];
if (nxt < 0) {
return;
}
idx = nxt;
for (const auto id : nodes[idx].accept) {
func(id);
}
}
return;
}
bool search(const std::string &str, int start, bool prefix = false) const {
int idx = 0;
for (int i = start; i < int(str.size()); ++i) {
int val = str[i] - margin;
assert(0 <= val && val < char_size);
int nxt = nodes[idx].nxt[val];
if (nxt < 0) {
return -1;
}
idx = nxt;
}
return prefix ? true : (nodes[idx].accept.size() > 0);
}
int size() const {
return int(nodes.size());
}
protected:
std::vector<trie_node> nodes;
};
} // namespace ebi
#line 12 "string/aho_corasick.hpp"
namespace ebi {
template <int char_size, int margin>
struct aho_corasick : trie<char_size + 1, margin> {
private:
void move_nxt(int &now, int val) {
assert(0 <= val && val < char_size);
while (this->nodes[now].nxt[val] == -1)
now = this->nodes[now].nxt[FAIL];
now = this->nodes[now].nxt[val];
return;
}
using trie<char_size + 1, margin>::trie;
using trie<char_size + 1, margin>::nodes;
public:
void build() {
correct.resize(this->size());
for (int i = 0; i < this->size(); ++i) {
correct[i] = int(this->nodes[i].accept.size());
}
std::queue<int> que;
for (int i = 0; i <= char_size; ++i) {
if (this->nodes[0].nxt[i] != -1) {
this->nodes[this->nodes[0].nxt[i]].nxt[FAIL] = 0;
que.push(this->nodes[0].nxt[i]);
} else {
this->nodes[0].nxt[i] = 0;
}
}
while (!que.empty()) {
int idx = que.front();
que.pop();
auto &now = this->nodes[idx];
correct[idx] += correct[now.nxt[FAIL]];
for (int i = 0; i < char_size; ++i) {
if (now.nxt[i] == -1) continue;
int fail = now.nxt[FAIL];
while (this->nodes[fail].nxt[i] == -1)
fail = this->nodes[fail].nxt[FAIL];
this->nodes[now.nxt[i]].nxt[FAIL] = this->nodes[fail].nxt[i];
std::vector<int> &u = this->nodes[now.nxt[i]].accept;
std::vector<int> &v =
this->nodes[this->nodes[fail].nxt[i]].accept;
std::vector<int> accept;
std::set_union(u.begin(), u.end(), v.begin(), v.end(),
std::back_inserter(accept));
u = accept;
que.push(now.nxt[i]);
}
}
}
std::map<int, int> match(const std::string &str, int now = 0) {
std::map<int, int> map;
for (const auto &c : str) {
move_nxt(now, c - margin);
for (const auto &a : this->nodes[now].accept) {
map[a]++;
}
}
return map;
}
template <class F> void query(const std::string &str, F func, int now = 0) {
for (int i = 0; i < int(str.size()); ++i) {
move_nxt(now, str[i] - margin);
for (const auto &a : this->nodes[now].accept) {
func(a, i);
}
}
return;
}
std::pair<int, int> move(const char &c, int now) {
int sum = 0;
move_nxt(now, c - margin);
sum += correct[now];
return {sum, now};
}
private:
const int FAIL = char_size;
std::vector<int> correct;
};
} // namespace ebi
#line 8 "test/aoj/aoj_2873.test.cpp"
int main() {
std::string s;
int n;
std::cin >> s >> n;
ebi::aho_corasick<26, 'a'> ac;
for (int i = 0; i < n; i++) {
std::string p;
std::cin >> p;
ac.add(p);
}
ac.build();
int now = 0;
int ans = 0;
for (auto c : s) {
auto [x, y] = ac.move(c, now);
if (x > 0) {
ans++;
now = 0;
} else {
now = y;
}
}
std::cout << ans << '\n';
}