Submission #1794770
Source Code Expand
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
//---------------------------------------------------------------------------------------------------
#define CMAX 26
#define OFFSET 'a'
struct Node {int nxt[CMAX + 1]; int exist; vector<int> accept;
Node() : exist(0) { memset(nxt, -1, sizeof(nxt)); }};
struct Trie {
vector<Node> nodes; int root;Trie() : root(0) { nodes.push_back(Node()); }
void upd_d(int node, int id) { nodes[node].accept.push_back(id); }
void upd_c(int node, int child, int id) { ++nodes[node].exist; }
void add(const string &str, int sindex, int nindex, int id){
if (sindex == str.size()) upd_d(nindex, id); else {const int c = str[sindex] - OFFSET;
if(nodes[nindex].nxt[c]==-1){nodes[nindex].nxt[c]=(int)nodes.size();nodes.push_back(Node());}
add(str, sindex + 1, nodes[nindex].nxt[c], id);upd_c(nindex, nodes[nindex].nxt[c], id);}}
void add(const string &str, int id) { add(str, 0, 0, id); }
void add(const string &str) { add(str, nodes[0].exist); }
int size() { return (nodes[0].exist); }int nodesize() { return ((int)nodes.size()); }};
struct AhoCorasick : Trie {
static const int FAIL = CMAX; vector<int> correct; AhoCorasick() : Trie() {}
void build() {correct.resize(nodes.size());
rep(i, 0, nodes.size()) correct[i] = (int)nodes[i].accept.size();
queue<int> que; rep(i, 0, CMAX + 1) { if (~nodes[0].nxt[i]) {
nodes[nodes[0].nxt[i]].nxt[FAIL] = 0;que.emplace(nodes[0].nxt[i]);}else nodes[0].nxt[i] = 0;}
while(!que.empty()){Node &now=nodes[que.front()];correct[que.front()]+=correct[now.nxt[FAIL]];
que.pop();for (int i = 0; i < CMAX; i++) {if (now.nxt[i] == -1) continue;
int fail = now.nxt[FAIL];while (nodes[fail].nxt[i] == -1) fail = nodes[fail].nxt[FAIL];
nodes[now.nxt[i]].nxt[FAIL] = nodes[fail].nxt[i];auto &u = nodes[now.nxt[i]].accept;
auto &v = nodes[nodes[fail].nxt[i]].accept;vector<int> accept;
set_union(begin(u), end(u), begin(v), end(v), back_inserter(accept));u = accept;
que.emplace(now.nxt[i]);}}}
int match(const string &str, vector< int > &result, int now = 0) {
result.assign(size(), 0);int count = 0;for (auto &c : str) {
while (nodes[now].nxt[c - OFFSET] == -1) now = nodes[now].nxt[FAIL];
now = nodes[now].nxt[c - OFFSET];count += correct[now];
for (auto &v : nodes[now].accept) ++result[v];}return count;}
int next(int now, char c) {while (nodes[now].nxt[c - OFFSET] == -1) now = nodes[now].nxt[FAIL];
return nodes[now].nxt[c - OFFSET];}
};
template<int MOD> struct ModInt {
static const int Mod = MOD; unsigned x; ModInt() : x(0) { }
ModInt(signed sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; }
ModInt(signed long long sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; }
int get() const { return (int)x; }
ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
ModInt &operator/=(ModInt that) { return *this *= that.inverse(); }
ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
ModInt inverse() const { long long a = x, b = MOD, u = 1, v = 0;
while (b) { long long t = a / b; a -= t * b; std::swap(a, b); u -= t * v; std::swap(u, v); }
return ModInt(u); }
bool operator==(ModInt that) const { return x == that.x; }
bool operator!=(ModInt that) const { return x != that.x; }
ModInt operator-() const { ModInt t; t.x = x == 0 ? 0 : Mod - x; return t; }
};
template<int MOD> ostream& operator<<(ostream& st, const ModInt<MOD> a) { st << a.get(); return st; };
template<int MOD> ModInt<MOD> operator^(ModInt<MOD> a, unsigned long long k) {
ModInt<MOD> r = 1; while (k) { if (k & 1) r *= a; a *= a; k >>= 1; } return r; }
typedef ModInt<1000000007> mint;
/*---------------------------------------------------------------------------------------------------
∧_∧
∧_∧ (´<_` ) Welcome to My Coding Space!
( ´_ゝ`) / ⌒i
/ \ | |
/ / ̄ ̄ ̄ ̄/ |
__(__ニつ/ _/ .| .|____
\/____/ (u ⊃
---------------------------------------------------------------------------------------------------*/
int N, M;
string S[101010], T;
mint dp[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
cin >> N;
AhoCorasick ac;
rep(i, 0, N) {
cin >> S[i];
ac.add(S[i]);
}
ac.build();
cin >> T;
M = T.size();
dp[0] = 1;
int s = ac.root;
rep(i, 0, M) {
s = ac.next(s, T[i]);
fore(j, ac.nodes[s].accept) dp[i + 1] += dp[i - S[j].size() + 1];
}
cout << dp[M].get() << endl;
}
Submission Info
Submission Time |
|
Task |
H - Separate String |
User |
hamayanhamayan |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
5629 Byte |
Status |
AC |
Exec Time |
365 ms |
Memory |
38888 KB |
Judge Result
Set Name |
All |
Score / Max Score |
100 / 100 |
Status |
|
Set Name |
Test Cases |
All |
00_sample_00, 00_sample_01, 00_sample_02, 00_sample_03, 10_rand_00, 10_rand_01, 10_rand_02, 10_rand_03, 10_rand_04, 11_rand_00, 11_rand_01, 11_rand_02, 11_rand_03, 11_rand_04, 20_fixed_length_00, 20_fixed_length_01, 20_fixed_length_02, 21_fixed_length_00, 21_fixed_length_01, 21_fixed_length_02, 22_fixed_length_00, 22_fixed_length_01, 22_fixed_length_02, 23_fixed_length_00, 23_fixed_length_01, 23_fixed_length_02, 24_fixed_length_00, 24_fixed_length_01, 24_fixed_length_02, 30_mixed_length_00, 30_mixed_length_01, 30_mixed_length_02, 30_mixed_length_03, 30_mixed_length_04, 90_challenge_00, 90_challenge_01, 90_challenge_02, 90_challenge_03, 90_challenge_04, 90_challenge_05 |
Case Name |
Status |
Exec Time |
Memory |
00_sample_00 |
AC |
2 ms |
1408 KB |
00_sample_01 |
AC |
2 ms |
1408 KB |
00_sample_02 |
AC |
2 ms |
1408 KB |
00_sample_03 |
AC |
2 ms |
1408 KB |
10_rand_00 |
AC |
47 ms |
38504 KB |
10_rand_01 |
AC |
42 ms |
37480 KB |
10_rand_02 |
AC |
56 ms |
37992 KB |
10_rand_03 |
AC |
47 ms |
36584 KB |
10_rand_04 |
AC |
24 ms |
19564 KB |
11_rand_00 |
AC |
51 ms |
37736 KB |
11_rand_01 |
AC |
50 ms |
38632 KB |
11_rand_02 |
AC |
53 ms |
38248 KB |
11_rand_03 |
AC |
51 ms |
38248 KB |
11_rand_04 |
AC |
54 ms |
37608 KB |
20_fixed_length_00 |
AC |
52 ms |
38248 KB |
20_fixed_length_01 |
AC |
54 ms |
38120 KB |
20_fixed_length_02 |
AC |
51 ms |
38888 KB |
21_fixed_length_00 |
AC |
46 ms |
38124 KB |
21_fixed_length_01 |
AC |
46 ms |
37996 KB |
21_fixed_length_02 |
AC |
47 ms |
37868 KB |
22_fixed_length_00 |
AC |
50 ms |
37224 KB |
22_fixed_length_01 |
AC |
51 ms |
37480 KB |
22_fixed_length_02 |
AC |
50 ms |
38504 KB |
23_fixed_length_00 |
AC |
49 ms |
37864 KB |
23_fixed_length_01 |
AC |
48 ms |
37224 KB |
23_fixed_length_02 |
AC |
53 ms |
36584 KB |
24_fixed_length_00 |
AC |
49 ms |
36836 KB |
24_fixed_length_01 |
AC |
46 ms |
37348 KB |
24_fixed_length_02 |
AC |
48 ms |
38756 KB |
30_mixed_length_00 |
AC |
49 ms |
37480 KB |
30_mixed_length_01 |
AC |
48 ms |
37352 KB |
30_mixed_length_02 |
AC |
47 ms |
38376 KB |
30_mixed_length_03 |
AC |
49 ms |
37864 KB |
30_mixed_length_04 |
AC |
48 ms |
37352 KB |
90_challenge_00 |
AC |
12 ms |
4276 KB |
90_challenge_01 |
AC |
365 ms |
2816 KB |
90_challenge_02 |
AC |
9 ms |
4276 KB |
90_challenge_03 |
AC |
151 ms |
2432 KB |
90_challenge_04 |
AC |
19 ms |
7672 KB |
90_challenge_05 |
AC |
2 ms |
1536 KB |