Submission #1799531
Source Code Expand
#include<iostream> #include<string> #include<vector> #include<queue> #include<stack> #include<map> #include<set> #include<algorithm> #include<functional> #include<cstdio> #include<cstdlib> #include<cmath> #include<cassert> #include<ctime> using namespace std; #define mind(a,b) (a>b?b:a) #define maxd(a,b) (a>b?a:b) #define absd(x) (x<0?-(x):x) #define pow2(x) ((x)*(x)) #define rep(i,n) for(int i=0; i<n; ++i) #define repr(i,n) for(int i=n-1; i>=0; --i) #define repl(i,s,n) for(int i=s; i<=n; ++i) #define replr(i,s,n) for(int i=n; i>=s; --i) #define repf(i,s,n,j) for(int i=s; i<=n; i+=j) #define repe(e,obj) for(auto e : obj) #define SP << " " << #define COL << " : " << #define COM << ", " << #define ARR << " -> " << #define PNT(STR) cout << STR << endl #define POS(X,Y) "(" << X << ", " << Y << ")" #define DEB(A) " (" << #A << ") " << A #define DEBREP(i,n,val) for(int i=0; i<n; ++i) cout << val << " "; cout << endl #define ALL(V) (V).begin(), (V).end() #define INF 1000000007 #define INFLL 1000000000000000007LL #define EPS 1e-9 typedef unsigned int uint; typedef unsigned long ulong; typedef unsigned long long ull; typedef long long ll; typedef long double ld; #define P_TYPE int typedef pair<P_TYPE, P_TYPE> P; typedef pair<P, P_TYPE> PI; typedef pair<P_TYPE, P> IP; typedef pair<P, P> PP; typedef priority_queue<P, vector<P>, greater<P> > pvqueue; #define NN 30 struct TrieNode { TrieNode(int size) : sz(size), cnt(0) { for(int i = 0; i < NN; ++i) next[i] = nullptr; suffix = nullptr; } TrieNode *next[NN]; TrieNode *suffix; int sz, cnt; }; TrieNode *root = new TrieNode(0); void add(string s) { TrieNode *node = root; for(int i = 0; i < s.length(); ++i) { int code = s[i] - 'a'; if(!node->next[code]) { node = node->next[code] = new TrieNode(node->sz + 1); } else { node = node->next[code]; } } node->cnt = 1; } void suffix() { queue<TrieNode*> que; que.push(root); while(!que.empty()) { TrieNode* v = que.front(); que.pop(); for(int i = 0; i< NN; ++i) { if(v->next[i] && v->sz < v->next[i]->sz) { if(v->suffix) { v->next[i]->suffix = v->suffix->next[i]; } else { v->next[i]->suffix = root; } que.push(v->next[i]); } else { if(v->suffix) { v->next[i] = v->suffix->next[i]; } else { if(root->next[i]) { v->next[i] = root->next[i]; } else { v->next[i] = root; } } } } } root->suffix = root; } #define MOD 1000000007 #define L 100003 ll dp[L]; int main() { int n; set<int> ls; vector<int> vs; vector<TrieNode*> state;//map<int, TrieNode*> state; cin >> n; for(int i = 0; i < n; ++i) { string s; cin >> s; add(s); ls.insert(s.length()); } suffix(); for(int l : ls) { vs.push_back(l); state.push_back(root); } string t; cin >> t; int tl = t.length(); dp[0] = 1; for(int i = 0; i < tl; ++i) { int code = t[i] - 'a'; for(int j=0; j < vs.size(); ++j) { int l = vs[j]; TrieNode *current = state[j] = state[j]->next[code]; if(current->sz == l) { if(current->cnt) { dp[i+1] += dp[i-l+1]; dp[i+1] %= MOD; } state[j] = current->suffix; } } } cout << dp[tl] << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | H - Separate String |
User | yaketake08 |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 3505 Byte |
Status | AC |
Exec Time | 396 ms |
Memory | 54144 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 | 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 | AC | 68 ms | 38528 KB |
10_rand_01 | AC | 74 ms | 42624 KB |
10_rand_02 | AC | 81 ms | 39424 KB |
10_rand_03 | AC | 86 ms | 48000 KB |
10_rand_04 | AC | 52 ms | 28160 KB |
11_rand_00 | AC | 99 ms | 53120 KB |
11_rand_01 | AC | 97 ms | 51840 KB |
11_rand_02 | AC | 97 ms | 53248 KB |
11_rand_03 | AC | 94 ms | 51200 KB |
11_rand_04 | AC | 94 ms | 50304 KB |
20_fixed_length_00 | AC | 83 ms | 41688 KB |
20_fixed_length_01 | AC | 82 ms | 41688 KB |
20_fixed_length_02 | AC | 87 ms | 41688 KB |
21_fixed_length_00 | AC | 63 ms | 53632 KB |
21_fixed_length_01 | AC | 62 ms | 53632 KB |
21_fixed_length_02 | AC | 63 ms | 53632 KB |
22_fixed_length_00 | AC | 86 ms | 51968 KB |
22_fixed_length_01 | AC | 88 ms | 51968 KB |
22_fixed_length_02 | AC | 88 ms | 51968 KB |
23_fixed_length_00 | AC | 83 ms | 54144 KB |
23_fixed_length_01 | AC | 83 ms | 54144 KB |
23_fixed_length_02 | AC | 84 ms | 54144 KB |
24_fixed_length_00 | AC | 77 ms | 52864 KB |
24_fixed_length_01 | AC | 77 ms | 52864 KB |
24_fixed_length_02 | AC | 77 ms | 52864 KB |
30_mixed_length_00 | AC | 76 ms | 53760 KB |
30_mixed_length_01 | AC | 76 ms | 53760 KB |
30_mixed_length_02 | AC | 76 ms | 53760 KB |
30_mixed_length_03 | AC | 77 ms | 53760 KB |
30_mixed_length_04 | AC | 77 ms | 53760 KB |
90_challenge_00 | AC | 26 ms | 3840 KB |
90_challenge_01 | AC | 396 ms | 1408 KB |
90_challenge_02 | AC | 22 ms | 3840 KB |
90_challenge_03 | AC | 253 ms | 1408 KB |
90_challenge_04 | AC | 21 ms | 6124 KB |
90_challenge_05 | AC | 1 ms | 256 KB |