結果
| 問題 | No.430 文字列検索 |
| ユーザー |
 Felerius
|
| 提出日時 | 2021-10-05 04:34:07 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 8 ms / 2,000 ms |
| コード長 | 8,398 bytes |
| コンパイル時間 | 3,020 ms |
| コンパイル使用メモリ | 227,936 KB |
| 実行使用メモリ | 6,560 KB |
| 最終ジャッジ日時 | 2023-09-30 08:27:07 |
| 合計ジャッジ時間 | 3,848 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge11 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
4,376 KB |
| testcase_01 | AC | 8 ms
6,560 KB |
| testcase_02 | AC | 3 ms
4,376 KB |
| testcase_03 | AC | 4 ms
4,380 KB |
| testcase_04 | AC | 1 ms
4,380 KB |
| testcase_05 | AC | 2 ms
4,380 KB |
| testcase_06 | AC | 1 ms
4,376 KB |
| testcase_07 | AC | 1 ms
4,376 KB |
| testcase_08 | AC | 2 ms
4,376 KB |
| testcase_09 | AC | 2 ms
4,376 KB |
| testcase_10 | AC | 1 ms
4,380 KB |
| testcase_11 | AC | 6 ms
4,840 KB |
| testcase_12 | AC | 7 ms
5,092 KB |
| testcase_13 | AC | 7 ms
5,232 KB |
| testcase_14 | AC | 6 ms
4,852 KB |
| testcase_15 | AC | 6 ms
4,848 KB |
| testcase_16 | AC | 5 ms
4,964 KB |
| testcase_17 | AC | 5 ms
5,112 KB |
ソースコード
// https://yukicoder.me/problems/1013
#pragma GCC optimize("fast-math")
// begin "cp-lib/prelude.hpp"
#include <bits/stdc++.h>
#ifdef LOCAL
# include <dbg.h>
#else
# define dbg(...) do {} while (0)
#endif
#define cp_lib_4th(_1, _2, _3, x, ...) x
#define cp_lib_rep(i, l, r) for (int i = (l); (i) < (r); ++(i))
#define cp_lib_rep0(i, r) cp_lib_rep(i, 0, r)
#define rep(...) cp_lib_4th(__VA_ARGS__, cp_lib_rep, cp_lib_rep0, _)(__VA_ARGS__)
#define cp_lib_repr(i, r, l, ...) for (int i = (r); (i) >= (l); --(i))
#define repr(...) cp_lib_repr(__VA_ARGS__, 0)
#define all(a) ::begin(a),::end(a)
#define trav(a, b) for (auto&& a : (b))
using namespace std;
using ll = long long;
using ld = long double;
[[maybe_unused]] static constexpr int INF = int(1e9 + 5);
[[maybe_unused]] static constexpr ll INFL = ll(INF) * INF;
template <class C> int sz(const C& c) { return int(::size(c)); }
// end "cp-lib/prelude.hpp"
// begin "cp-lib/io.hpp"
// begin "_assert.hpp"
#ifdef CP_LIB_DEBUG
#define cp_lib_assert(expr) \
do { if (!(expr)) { \
::cerr << "assertion failed: " << #expr << " (" << __FILE__ << ':' << __LINE__ << ")\n"; \
::abort(); \
} } while (0)
#else
#define cp_lib_assert(expr)
#endif
// end "_assert.hpp"
// begin "modint/_detect.hpp"
namespace cp_lib_modint { struct ModIntTag {}; }
// end "modint/_detect.hpp"
#include <unistd.h>
namespace cp_lib_io {
constexpr int BUF_SIZE = 1 << 20;
array<char, BUF_SIZE> ibuf, obuf;
char *iptr = data(ibuf), *iend = iptr, *optr = data(obuf);
template <class T, class = void> struct is_tuple_like : false_type {};
template <class T> struct is_tuple_like<T, void_t<tuple_element_t<0, T>>> : true_type {};
template <class T> struct is_std_array : false_type {};
template <class T, size_t I> struct is_std_array<array<T, I>> : true_type {};
void flush() { write(STDOUT_FILENO, begin(obuf), optr - begin(obuf)); optr = begin(obuf); }
void ensure_write(int l) { if (end(obuf) - optr < l) flush(); }
int _flush_atexit = []{ atexit(flush); return 0; }();
void refill() {
memmove(begin(ibuf), iptr, iend - iptr);
iend -= iptr - begin(ibuf);
iptr = begin(ibuf);
iend += read(STDIN_FILENO, iend, end(ibuf) - iend);
}
void skip_ensure_read(int l) {
do {
while (iptr != iend && *iptr <= ' ') ++iptr;
if (iend - iptr < l) refill();
} while (*iptr <= ' ');
}
template <class T, class T2 = remove_reference_t<remove_cv_t<T>>>
void print(T&& val) {
if constexpr (is_same_v<T2, char>)
ensure_write(2), *optr++ = val;
else if constexpr (is_integral_v<T2> && !is_same_v<T2, bool>) {
ensure_write(numeric_limits<T>::digits10 + 1 + is_signed_v<T2>);
if (val < 0) { *optr++ = '-'; print(make_unsigned_t<T2>(-make_unsigned_t<T2>(val))); return; }
array<char, 128> tmp;
char* tptr = end(tmp);
remove_const_t<T2> val_copy = val;
do { *--tptr = char('0' + val_copy % 10), val_copy /= 10; } while (val_copy);
memcpy(optr, tptr, end(tmp) - tptr);
optr += end(tmp) - tptr;
#if __cpp_lib_to_chars >= 201611
} else if constexpr (is_floating_point_v<T2>) {
ensure_write(64);
auto res = to_chars(optr, end(obuf), val, chars_format::fixed, 30);
cp_lib_assert(res.ec == errc());
optr = res.ptr;
#endif
} else if constexpr (is_convertible_v<T, string_view>) {
string_view sv(val);
if (sz(sv) + 1 <= end(obuf) - optr)
memcpy(optr, data(sv), sz(sv)), optr += sz(sv);
else
flush(), write(STDOUT_FILENO, data(sv), sz(sv));
} else {
if constexpr (is_same_v<T2, bool> || is_same_v<T2, vector<bool>::reference>)
print(int(val));
else if constexpr (is_base_of_v<cp_lib_modint::ModIntTag, T2>)
print(decltype(T2::mod())(val));
else if constexpr (is_tuple_like<T2>() && !is_std_array<T2>())
apply([](auto&&... items) { (print(items), ...); }, forward<T>(val));
else
trav(item, val) print(item);
return;
}
*optr++ = ' ';
}
template <class T>
void read(T& val) {
if constexpr (is_same_v<T, char>)
skip_ensure_read(1), val = *iptr++;
else if constexpr (is_same_v<T, bool> || is_same_v<T, vector<bool>::reference>) {
uint8_t ival; read(ival), val = bool(ival);
} else if constexpr (is_base_of_v<cp_lib_modint::ModIntTag, T>) {
ll ival; read(ival); val = T(ival);
} else if constexpr (is_integral_v<T>) {
skip_ensure_read(numeric_limits<T>::digits10 + 1 + is_signed_v<T>);
if (is_signed_v<T> && *iptr == '-') {
++iptr;
make_unsigned_t<T> uval;
read(uval);
val = T(-uval);
} else {
val = 0;
while (iptr != iend && *iptr > ' ') val = T(10 * val + (*iptr++ - '0'));
}
#if __cpp_lib_to_chars >= 201611
} else if constexpr (is_floating_point_v<T>) {
skip_ensure_read(128);
auto res = from_chars(iptr, iend, val);
assert(res.ec == errc());
iptr = const_cast<char*>(res.ptr);
#endif
} else if constexpr (is_same_v<T, string>) {
val = string();
skip_ensure_read(1);
do {
auto* after = iptr;
while (after != iend && *after > ' ') ++after;
copy(iptr, after, back_inserter(val));
if ((iptr = after) == iend)
refill();
else
break;
} while (iptr != iend);
} else if constexpr (is_tuple_like<T>() && !is_std_array<T>())
apply([](auto&... items) { (read(items), ...); }, val);
else
trav(item, val) read(item);
}
}
using cp_lib_io::flush;
template <class... Args>
void print(Args&&... args) { (cp_lib_io::print(forward<Args>(args)), ...); }
template <class... Args>
void println(Args&&... args) {
if (sizeof...(Args) > 0)
(cp_lib_io::print(forward<Args>(args)), ...), *(cp_lib_io::optr - 1) = '\n';
else
cp_lib_io::ensure_write(1), *cp_lib_io::optr++ = '\n';
}
template <class... Args>
void printlns(Args&&... args) {
((cp_lib_io::print(forward<Args>(args)), *(cp_lib_io::optr - 1) = '\n'), ...);
}
template <class... Args>
void read(Args&... args) { (cp_lib_io::read(args), ...); }
// end "cp-lib/io.hpp"
// begin "cp-lib/string/aho-corasick.hpp"
template <int K = 26>
class AhoCorasick {
vector<array<int, K>> t = {array<int, K>{}};
int base;
public:
AhoCorasick(int base_ = 'a') : base(base_) {}
size_t size() const { return ::size(t); }
int next(int v, int c) const { return t[v][c - base]; }
int& next(int v, int c) { return t[v][c - base]; }
template <class It, class ItEnd>
int add(It it, ItEnd it_end) {
int v = 0;
for (; it != it_end; v = t[v][*it++ - base])
if (!t[v][*it - base])
t[v][*it - base] = sz(t), t.emplace_back().fill(0);
return v;
}
template <class F>
void build(F&& f) {
queue<array<int, 4>> q;
q.push({0, -1, 0, -1});
while (sz(q)) {
auto [v, c, p, plink] = q.front(); q.pop();
int link = (p ? t[plink][c] : 0);
rep(c2, K) {
if (t[v][c2])
q.push({t[v][c2], c2, v, link});
else
t[v][c2] = (v ? t[link][c2] : 0);
}
f(v, link, c, p);
}
}
};
// end "cp-lib/string/aho-corasick.hpp"
int main() {
string s; int n; read(s, n);
AhoCorasick ac('A');
vector<int> endcnt;
rep(_, n) {
string c; read(c);
int v = ac.add(all(c));
endcnt.resize(sz(ac));
endcnt[v]++;
}
ac.build([&](int v, int link, int, int) {
endcnt[v] += endcnt[link];
});
int v = 0, ans = 0;
trav(c, s)
v = ac.next(v, c), ans += endcnt[v];
println(ans);
}