Submission #3106971
Source Code Expand
#include <bits/stdc++.h> using namespace std; using ll = long long; // never fail to call build() !! // constructor() // add(string) // match(string) : [left, right], vec<tuple<int left, int right, int key>> in // right-order /// --- AhoCorasick Library {{{ /// struct AhoCorasick { struct Trie { unordered_map< char, Trie* > child; Trie* failure = nullptr; Trie* next = nullptr; // next failure that has the word // vector< int > words; int word = -1; Trie* add(char c) { if(child.count(c)) { return child[c]; } else { return child[c] = new Trie; } } Trie* go(char c) { if(child.count(c)) { return child[c]; } else { if(failure == nullptr) { // only top return this; } else { return failure->go(c); } } } }; Trie* top = new Trie; vector< string > dict; void add(string word) { Trie* now = top; for(size_t i = 0; i < word.size(); i++) { now = now->add(word[i]); } now->word = dict.size(); dict.emplace_back(word); } void build() { queue< Trie* > q; q.emplace(top); while(q.size()) { Trie* now = q.front(); q.pop(); for(pair< char, Trie* > ch : now->child) { q.emplace(ch.second); Trie* failure = ch.second->failure = now == top ? top : now->failure->go(ch.first); ch.second->next = failure->word >= 0 ? failure : failure->next; } } } vector< tuple< int, int, int > > match(string s) { Trie* now = top; vector< tuple< int, int, int > > res; for(size_t i = 0; i < s.size(); i++) { now = now->go(s[i]); Trie* tmp = now; do { int word = tmp->word; if(word >= 0) { res.emplace_back(i - dict[word].size() + 1, i, word); tmp = tmp->next; } } while(tmp != nullptr && tmp != top); } return res; } }; /// }}}--- /// int main() { std::ios::sync_with_stdio(false), std::cin.tie(0); int n; cin >> n; AhoCorasick ecasd; for(int i = 0; i < n; i++) { string t; cin >> t; ecasd.add(t); } ecasd.build(); string s; cin >> s; int m = s.size(); auto matches = ecasd.match(s); const int mod = 1e9 + 7; vector< ll > dp(m + 1); dp[0] = 1; for(auto p : matches) { int le, ri, key; tie(le, ri, key) = p; dp[ri + 1] = (dp[ri + 1] + dp[le]) % mod; } cout << dp[m] << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | H - Separate String |
User | luma |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2567 Byte |
Status | TLE |
Exec Time | 2106 ms |
Memory | 788576 KB |
Judge Result
Set Name | All | ||||||
---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 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 | 1 ms | 256 KB |
00_sample_01 | AC | 1 ms | 256 KB |
00_sample_02 | AC | 1 ms | 256 KB |
00_sample_03 | AC | 1 ms | 256 KB |
10_rand_00 | TLE | 2105 ms | 23168 KB |
10_rand_01 | TLE | 2105 ms | 25088 KB |
10_rand_02 | TLE | 2105 ms | 23552 KB |
10_rand_03 | TLE | 2106 ms | 28288 KB |
10_rand_04 | TLE | 2104 ms | 16640 KB |
11_rand_00 | TLE | 2106 ms | 31360 KB |
11_rand_01 | TLE | 2104 ms | 32640 KB |
11_rand_02 | TLE | 2106 ms | 31360 KB |
11_rand_03 | TLE | 2106 ms | 30208 KB |
11_rand_04 | TLE | 2106 ms | 29696 KB |
20_fixed_length_00 | TLE | 2104 ms | 27004 KB |
20_fixed_length_01 | TLE | 2105 ms | 24956 KB |
20_fixed_length_02 | TLE | 2105 ms | 24956 KB |
21_fixed_length_00 | TLE | 2106 ms | 32000 KB |
21_fixed_length_01 | TLE | 2106 ms | 32000 KB |
21_fixed_length_02 | TLE | 2105 ms | 34048 KB |
22_fixed_length_00 | TLE | 2106 ms | 30720 KB |
22_fixed_length_01 | TLE | 2106 ms | 30720 KB |
22_fixed_length_02 | TLE | 2106 ms | 30720 KB |
23_fixed_length_00 | TLE | 2104 ms | 33920 KB |
23_fixed_length_01 | TLE | 2106 ms | 31872 KB |
23_fixed_length_02 | TLE | 2106 ms | 31872 KB |
24_fixed_length_00 | TLE | 2106 ms | 31360 KB |
24_fixed_length_01 | TLE | 2104 ms | 33408 KB |
24_fixed_length_02 | TLE | 2106 ms | 31360 KB |
30_mixed_length_00 | TLE | 2106 ms | 31616 KB |
30_mixed_length_01 | TLE | 2106 ms | 31616 KB |
30_mixed_length_02 | TLE | 2106 ms | 31616 KB |
30_mixed_length_03 | TLE | 2106 ms | 31616 KB |
30_mixed_length_04 | TLE | 2106 ms | 31616 KB |
90_challenge_00 | TLE | 2103 ms | 2304 KB |
90_challenge_01 | MLE | 1161 ms | 788576 KB |
90_challenge_02 | TLE | 2103 ms | 2304 KB |
90_challenge_03 | AC | 605 ms | 394596 KB |
90_challenge_04 | AC | 29 ms | 11756 KB |
90_challenge_05 | TLE | 2103 ms | 256 KB |