結果
| 問題 | No.430 文字列検索 |
| コンテスト | |
| ユーザー |
 ああ
|
| 提出日時 | 2026-06-05 10:05:48 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 15 ms / 2,000 ms |
| コード長 | 15,741 bytes |
| 記録 | |
| コンパイル時間 | 5,664 ms |
| コンパイル使用メモリ | 355,772 KB |
| 実行使用メモリ | 10,960 KB |
| 最終ジャッジ日時 | 2026-06-05 10:05:55 |
| 合計ジャッジ時間 | 7,002 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge1_1 |
| 純コード判定待ち |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 14 |
ソースコード
#include <iostream>
#include <vector>
#include <ranges>
#include <iomanip>
#include <algorithm>
#include <math.h>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <bit>
#include <atcoder/all>
#include <random>
#include <ext/pb_ds/assoc_container.hpp>
#define rep(n, i) for (int i = 0; i < n; i++)
#define rep2(start, end, i) for (int i = start; i < end; i++)
#define rep3(start, end, step, i) for (int i = start; i < end; i+=step)
#define reprev(n, i) for (int i = n-1; i >= 0; i--)
#define reprev2(start, end, i) for (int i = start-1; i >= end; i--)
#define reprev3(start, end, step, i) for (int i = start-1; i >= end; i-=step)
using namespace std;
using namespace atcoder;
using ll = long long;
using ull = unsigned long long;
using mint = modint998244353;
template <typename T, typename V = __gnu_pbds::null_type, typename Cmp_Fn = less<T>>
using ost = __gnu_pbds::tree<T, V, Cmp_Fn,
__gnu_pbds::rb_tree_tag,
__gnu_pbds::tree_order_statistics_node_update>;
void yes() {
cout << "Yes" << endl;
}
void no() {
cout << "No" << endl;
}
void yesno(bool yes) {
yes ? ::yes() : no();
}
void noyes(bool no) {
yesno(!no);
}
bool inrange(int i, int j, int h, int w) {
return 0 <= i && i < h && 0 <= j && j < w;
}
template <typename T>
T isqrt(T n) {
if (n == 0) return 0;
T temp = sqrt(n) - 1;
return temp * (temp + 2) < n ? temp + 1 : temp;
}
template <typename T=int>
T power(T x, int n) {
T ret = 1;
rep(n, i) {
ret *= x;
}
return ret;
}
template <typename T, typename U, typename V>
struct triple {
T first;
U second;
V third;
auto operator<=>(const triple&) const = default;
};
struct Dir {
int i;
int j;
string word;
};
vector<Dir> dirs1{
{0, 1, "R"},
{1, 0, "D"},
{-1, 0, "U"},
{0, -1, "L"}
};
vector<Dir> dirs2{
{-1, 1, "UR"},
{1, 1, "DR"},
{-1, -1, "UL"},
{1, -1, "DL"},
};
// インデックス i の逆方向が (7 - i) になるように配置した8方向
vector<Dir> dirs3{
{-1, 0, "U"}, // 0: 上 <---> 7: 下
{-1, 1, "UR"}, // 1: 右上 <---> 6: 左下
{ 0, 1, "R"}, // 2: 右 <---> 5: 左
{ 1, 1, "DR"}, // 3: 右下 <---> 4: 左上
{-1, -1, "UL"}, // 4: 左上 <---> 3: 右下
{ 0, -1, "L"}, // 5: 左 <---> 2: 右
{ 1, -1, "DL"}, // 6: 左下 <---> 1: 右上
{ 1, 0, "D"} // 7: 下 <---> 0: 上
};
template <typename T=int>
struct Trie {
struct node {
T prefix;
T term;
int nxt[26];
};
vector<node> nodes{node{}};
int get(const string& s) {
int cur = 0;
for (char c: s) {
auto nxt = nodes[cur].nxt[c - 'a'];
if (nxt == 0) {
return -1;
} else {
cur = nxt;
}
}
return cur;
}
void add(const string& s, T x) {
int cur = 0;
nodes[cur].prefix += x;
for (char c: s) {
int nxt = nodes[cur].nxt[c - 'a'];
if (nxt == 0) {
nodes.push_back(node{});
nodes[cur].nxt[c - 'a'] = nodes.size() - 1;
}
cur = nodes[cur].nxt[c - 'a'];
nodes[cur].prefix += x;
}
nodes[cur].term += x;
}
};
template <typename T = int>
struct Lca {
int n, l{0};
vector<int> depth;
vector<vector<int>> to, par;
vector<vector<T>> co;
vector<T> costs;
Lca(int n): n(n), depth(n), to(n), par(n), co(n), costs(n) {
while((1 << l) < n) ++l;
par.assign(n+1, vector(l, n));
}
void addEdge(int a, int b, T c = 0) {
to[a].push_back(b);
co[a].push_back(c);
to[b].push_back(a);
co[b].push_back(c);
}
void init() {
dfs(0, n, 0, 0);
for (int i = 0; i < l-1; i++) {
for (int u = 0; u < n; u++) {
par[u][i+1] = par[par[u][i]][i];
}
}
}
int up(int u, int k) {
for (int i = l-1; i >= 0; i--) {
int len = 1 << i;
if (len <= k) {
k -= len;
u = par[u][i];
}
}
return u;
}
int point(int u, int v) {
if (depth[v] < depth[u]) swap(u, v);
v = up(v, depth[v] - depth[u]);
if (u == v) return u;
for (int i = l-1; i >= 0; i--) {
if (par[u][i] != par[v][i]) {
u = par[u][i];
v = par[v][i];
}
}
return par[u][0];
}
int dist(int u, int v) {return depth[u] + depth[v] - 2 * depth[point(u, v)];}
int cost(int u, int v) {return costs[u] + costs[v] - 2 * costs[point(u, v)];}
bool onPath(int u, int v, int w) {return dist(u, w) + dist(w, v) == dist(u, v);}
private:
void dfs(int u, int p, int d, T c) {
depth[u] = d;
costs[u] = c;
par[u][0] = p;
for (int i = 0; i < to[u].size(); i++) {
if (to[u][i] == p) continue;
dfs(to[u][i], u, d+1, c+co[u][i]);
}
}
};
template <typename T=int>
struct Minplus {
T val{};
bool inf = true;
Minplus() = default;
Minplus(T val): val(val), inf(false) {};
Minplus& operator+=(const Minplus& rhs) {
*this = *this + rhs;
return *this;
}
Minplus operator+(const Minplus& rhs) {
if (inf) {
return rhs;
} else if (rhs.inf) {
return *this;
} else {
return Minplus(min(val, rhs.val));
}
}
Minplus& operator*=(const Minplus& rhs) {
*this = *this * rhs;
return *this;
}
Minplus operator*(const Minplus& rhs) {
if (inf || rhs.inf) {
return Minplus();
} else {
return Minplus(val + rhs.val);
}
}
friend ostream& operator<<(ostream& os, const Minplus& rhs) {
if (rhs.inf) {
os << "inf";
} else {
os << rhs.val;
}
return os;
}
};
template <typename T>
struct Mulid { static T get() {return T(1);} };
template <typename T>
struct Mulid<Minplus<T>> { static T get() {return T(0);} };
template <typename T=int>
struct Mat {
int h;
int w;
vector<vector<T>> data;
Mat(int h, int w): h(h), w(w), data(h, vector(w, T{})) {};
Mat(const vector<vector<T>>& data): h(data.size()), w(data[0].size()), data(data) {};
Mat(const initializer_list<initializer_list<T>>& d): h(d.size()), w(d.begin()->size()) {
for (auto row: d) {
data.emplace_back(row);
}
};
static Mat e(int n) {
Mat ret = Mat(n, n);
rep(n, i) {
ret.data[i][i] = Mulid<T>::get();
}
return ret;
}
friend ostream& operator<<(ostream& os, const Mat& m) {
os << "Mat {" << endl;
rep(m.h, i) {
rep(m.w, j) {
os << m.data[i][j] << ", ";
}
os << endl;
}
os << "}";
return os;
}
Mat& operator*=(const Mat& rhs) {
*this = *this * rhs;
return *this;
}
Mat operator*(const Mat& m) {
assert(w == m.h);
Mat ret(h, m.w);
rep(h, i) {
rep(m.w, j) {
rep(w, k) {
ret.data[i][j] += data[i][k] * m.data[k][j];
}
}
}
return ret;
}
template <typename V>
Mat pow(V n) {
assert(h == w);
Mat ret = e(h);
Mat cur = *this;
while (n > 0) {
if (n & 1) {
ret *= cur;
}
cur *= cur;
n >>= 1;
}
return ret;
}
};
template <char start = 'a', char end = 'z'>
struct Aho {
static constexpr int size = end - start + 1;
struct node {
bool term;
int fail;
int in;
int out;
int nxt[size];
int move[size];
};
vector<node> nodes = {node{}};
vector<int> ids;
vector<int> cnt;
void add(const string& s) {
int cur = 0;
for (auto c: s) {
if (nodes[cur].nxt[c - start] == 0) {
nodes.push_back(node{});
nodes[cur].nxt[c - start] = nodes.size() - 1;
}
cur = nodes[cur].nxt[c - start];
}
nodes[cur].term = true;
ids.push_back(cur);
}
void init() {
deque<int> que;
rep(size, i) {
int nxt = nodes[0].nxt[i];
if (nxt != 0) {
nodes[0].move[i] = nxt;
nodes[0].in++;
que.push_back(nxt);
}
}
while (!que.empty()) {
int u = que.front();
que.pop_front();
int out = nodes[nodes[u].fail].term ? nodes[u].fail : nodes[nodes[u].fail].out;
nodes[u].out = out;
nodes[out].in++;
rep(size, i) {
nodes[u].move[i] = nodes[nodes[u].fail].move[i];
int nxt = nodes[u].nxt[i];
if (nxt != 0) {
nodes[u].move[i] = nxt;
int fail = nodes[nodes[u].fail].move[i];
nodes[nxt].fail = fail;
que.push_back(nxt);
}
}
}
}
void search(const string& s) {
cnt = vector(nodes.size(), 0);
int cur = 0;
for (auto c: s) {
cur = nodes[cur].move[c - start];
cnt[cur]++;
}
vector<int> que;
vector<int> tin(nodes.size());
rep(nodes.size(), i) {
tin[i] = nodes[i].in;
if (tin[i] == 0) {
que.push_back(i);
}
}
while (!que.empty()) {
int u = que.back();
que.pop_back();
int nxt = nodes[u].out;
cnt[nxt] += cnt[u];
tin[nxt]--;
if (tin[nxt] == 0) {
que.push_back(nxt);
}
}
}
int count(int id) {
return cnt[ids[id]];
}
};
// ostream& operator<<(ostream&os, const mint m);
// template <typename T, typename V>
// ostream& operator<<(ostream& os, const pair<T, V>& p);
// template <typename T, typename U, typename V>
// ostream& operator<<(ostream& os, const tuple<T,U,V>& t);
// template <typename T>
// ostream& operator<<(ostream& os, const vector<T>& v);
// template <typename T>
// ostream& operator<<(ostream& os, const set<T>& s);
// template <typename T, typename V>
// ostream& operator<<(ostream& os, const map<T, V>& m);
// template <typename T>
// ostream& operator<<(ostream& os, const deque<T>& v);
// template <typename T, typename V = __gnu_pbds::null_type, typename Cmp_Fn = less<T>>
// ostream& operator<<(ostream& os, const ost<T,V,Cmp_Fn>& ost);
// template <typename T, typename U, typename V>
// ostream& operator<<(ostream& os, const triple<T, U, V>& triple);
// template <typename T>
// ostream& operator<<(ostream& os, const Mat<T>& Mat);
template <typename T, typename V, typename Cmp_Fn>
ostream& operator<<(ostream& os, const ost<T, V, Cmp_Fn> &t) {
os << "ost {";
for (auto it = t.begin(); it != t.end(); ++it) {
os << *it;
if (next(it) != t.end()) {
os << ", ";
}
}
os << "}";
return os;
}
ostream& operator<<(ostream& os, const mint m) {
os << m.val();
return os;
}
template <typename T, typename V>
ostream& operator<<(ostream& os, const pair<T, V>& p) {
os << "(" << p.first << ", " << p.second << ")";
return os;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
os << "[";
rep(v.size(), i) {
os << v[i];
if (i != v.size()-1) {
os << ", ";
}
}
os << "]";
return os;
}
template <typename T>
ostream& operator<<(ostream& os, const set<T>& s) {
os << "set";
os << vector(s.begin(), s.end());
return os;
}
template <typename T, typename V>
ostream& operator<<(ostream& os, const map<T, V>& m) {
os << "map";
os << vector(m.begin(), m.end());
return os;
}
template <typename T>
ostream& operator<<(ostream& os, const deque<T>& v) {
os << "deque([";
rep(v.size(), i) {
os << v[i];
if (i != v.size()-1) {
os << ", ";
}
}
os << "])";
return os;
}
template <typename T, typename U, typename V>
ostream& operator<<(ostream& os, const triple<T, U, V>& triple) {
os << "triple{";
os << triple.first << ", " << triple.second << ", " << triple.third << "}";
return os;
}
vector<mint> inv;
vector<mint> finv;
vector<mint> fact;
void cominit(int n) {
inv.assign(n+1, 0);
finv.assign(n+1, 0);
fact.assign(n+1, 0);
inv[1] = 1;
finv[0] = 1; finv[1] = 1;
fact[0] = 1; fact[1] = 1;
rep2(2, n+1, i) {
inv[i] = -inv[mint::mod() % i] * (mint::mod() / i);
finv[i] = finv[i-1] * inv[i];
fact[i] = fact[i-1] * i;
}
}
mint com(int n, int k) {
if (n < 0 || k < 0 || n < k) {
return 0;
} else {
return fact[n] * finv[k] * finv[n-k];
}
}
template <typename T=int>
mint com2(T n, int k) {
if (n <= 0 || k < 0 || n < k) {
return 0;
} else {
mint ret = 1;
rep(k, i) {
ret *= n - i;
ret /= k - i;
}
return ret;
}
}
template <typename Container, typename V=int>
vector<pair<typename Container::value_type, V>> rle(const Container& con) {
using Element = typename Container::value_type;
vector<pair<Element, V>> ret;
if (con.empty()) return ret;
Element cur = con[0];
V cnt{1};
rep2(1, con.size(), i) {
if (con[i] == cur) ++cnt;
else {
ret.push_back({cur, cnt});
cur = con[i];
cnt = 1;
}
}
ret.push_back({cur, cnt});
return ret;
}
template <ranges::range R>
void outrange(const R& r, const string& sep) {
auto it = ranges::begin(r);
auto last = ranges::end(r);
ostringstream oss;
if (it != last) oss << *it++;
for (; it != last; ++it) {
oss << sep << *it;
}
cout << oss.str() << endl;
}
vector<int> minfact;
void pfactinit(int n) {
minfact.assign(n+1,0);
rep2(2,n+1,i) {
if (minfact[i] != 0) continue;
minfact[i] = i;
rep3(i,n+1,i,j) if (minfact[j] == 0) minfact[j] = i;
}
}
vector<pair<int,int>> pfact(int n) {
vector<pair<int,int>> factors;
while (minfact[n] != 0) {
int fact = minfact[n];
int cnt{0};
while (minfact[n] == fact) {
n /= fact;
++cnt;
}
factors.push_back({fact,cnt});
}
return factors;
}
int main() {
string s;
int m;
cin >> s >> m;
Aho<'A', 'Z'> aho;
rep(m, i) {
string c;
cin >> c;
aho.add(c);
}
aho.init();
aho.search(s);
int ans = 0;
rep(m, i) {
ans += aho.count(i);
}
cout << ans << endl;
// int n, k;
// cin >> n >> k;
// Aho aho;
// rep(k, i) {
// string s;
// cin >> s;
// aho.add(s);
// }
// aho.init();
// Mat<mint> mat(aho.nodes.size(), aho.nodes.size());
// rep(aho.nodes.size(), i) {
// if (aho.nodes[i].term) continue;
// rep(26, j) {
// mat.data[aho.nodes[i].move[j]][i]++;
// }
// }
// Mat<mint> first(aho.nodes.size(), 1);
// first.data[0][0] = 1;
// Mat res = mat.pow(n) * first;
// mint ans;
// rep(aho.nodes.size(), i) {
// if (!aho.nodes[i].term) {
// ans += res.data[i][0];
// }
// }
// cout << ans << endl;
}