Resources:
return zero
CP-Algorithms
Codechef camp video
GeeksForGeeks
open genus
toptal/aho-corasick-algorithm
CFblog-1 Cfblog-2 CF_blog-3
A2Online judge probles list
Implementation: problem link
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| using namespace std; | |
| #define INF 1<<30 | |
| #define endl '\n' | |
| #define maxn 100005 | |
| #define tc printf("Case %d: ", cs) | |
| #define tcn printf("Case %d:\n", cs); | |
| #define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); | |
| typedef long long ll; | |
| const double PI = acos(-1.0); | |
| #define dbg1(x) cerr << #x << " = " << x << endl; | |
| #define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl; | |
| #define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl; | |
| #define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl; | |
| // template < typename F, typename S > | |
| // ostream& operator << ( ostream& os, const pair< F, S > & p ) { | |
| // return os << "(" << p.first << ", " << p.second << ")"; | |
| // } | |
| // template < typename T > | |
| // ostream &operator << ( ostream & os, const vector< T > &v ) { | |
| // os << "{"; | |
| // for (auto it = v.begin(); it != v.end(); ++it) { | |
| // if ( it != v.begin() ) os << ", "; | |
| // os << *it; | |
| // } | |
| // return os << "}"; | |
| // } | |
| // template < typename T > | |
| // ostream &operator << ( ostream & os, const set< T > &v ) { | |
| // os << "["; | |
| // for (auto it = v.begin(); it != v.end(); ++it) { | |
| // if ( it != v.begin()) os << ", "; | |
| // os << *it; | |
| // } | |
| // return os << "]"; | |
| // } | |
| // template < typename F, typename S > | |
| // ostream &operator << ( ostream & os, const map< F, S > &v ) { | |
| // os << "["; | |
| // for (auto it = v.begin(); it != v.end(); ++it) { | |
| // if ( it != v.begin() ) os << ", "; | |
| // os << it -> first << " = " << it -> second ; | |
| // } | |
| // return os << "]"; | |
| // } | |
| // #define dbg(args...) do {cerr << #args << " : "; faltu(args); } while(0) | |
| // clock_t tStart = clock(); | |
| // #define timeStamp dbg("Execution Time: ", (double)(clock() - tStart)/CLOCKS_PER_SEC) | |
| // void faltu () { cerr << endl; } | |
| // template <typename T> | |
| // void faltu( T a[], int n ) { | |
| // for (int i = 0; i < n; ++i) cerr << a[i] << ' '; | |
| // cerr << endl; | |
| // } | |
| // template <typename T, typename ... hello> | |
| // void faltu( T arg, const hello &... rest) { cerr << arg << ' '; faltu(rest...); } | |
| // // Program showing a policy-based data structure. | |
| // #include <ext/pb_ds/assoc_container.hpp> // Common file | |
| // #include <ext/pb_ds/tree_policy.hpp> | |
| // #include <functional> // for less | |
| // #include <iostream> | |
| // using namespace __gnu_pbds; | |
| // using namespace std; | |
| // // GNU link : https://goo.gl/WVDL6g | |
| // typedef tree<int, null_type, less_equal<int>, rb_tree_tag, | |
| // tree_order_statistics_node_update> | |
| // new_data_set; | |
| // /**___________________________________________________**/ | |
| const int N = 1e6 + 6; | |
| const int M = 505; | |
| const int nx = 2e5 + 5; | |
| struct node | |
| { | |
| int link[27]; | |
| node() | |
| { | |
| memset(link, -1, sizeof link); | |
| } | |
| }; | |
| node a[N];//2e5 | |
| char s[N];//1e6 | |
| char ch[M];// 505 | |
| int suffix[N];//2e5 | |
| int val[N];//2e5 | |
| int path[N]; //2e5 | |
| int en[M]; //505 | |
| int num; | |
| int koto = 0; | |
| void init() | |
| { | |
| memset(a, -1, sizeof a); | |
| memset(suffix, 0, sizeof suffix); | |
| memset(val, 0, sizeof val); | |
| memset(path, 0, sizeof path); | |
| num = 0; | |
| koto = 0; | |
| } | |
| void makeTrie(int j, int l) | |
| { | |
| int cur = 0; | |
| for (int i = 1; i <= l; i++) { | |
| int x = ch[i] - 96; | |
| if (a[cur].link[x] == (-1)) { | |
| a[cur].link[x] = ++num; | |
| } | |
| cur = a[cur].link[x]; | |
| } | |
| en[j] = cur; | |
| } | |
| void bfs() | |
| { | |
| queue<int> Q; | |
| for (int i = 1; i <= 26; i++) { | |
| if (a[0].link[i] == -1) { | |
| a[0].link[i] = 0; | |
| } | |
| else { | |
| Q.push(a[0].link[i]); | |
| suffix[a[0].link[i]] = 0; | |
| } | |
| } | |
| while (!Q.empty()) { | |
| int u = Q.front(); | |
| Q.pop(); | |
| for (int i = 1; i <= 26; i++) { | |
| int v = a[u].link[i]; | |
| if (v == -1) { | |
| a[u].link[i] = a[suffix[u]].link[i]; | |
| } | |
| else { | |
| Q.push(v); | |
| suffix[v] = a[suffix[u]].link[i]; | |
| path[++koto] = v; | |
| } | |
| } | |
| } | |
| } | |
| void search(int l) | |
| { | |
| int cur = 0; | |
| for (int i = 1; i <= l; i++) { | |
| int x = s[i] - 96; | |
| cur = a[cur].link[x]; | |
| val[cur]++; | |
| } | |
| for (int i = koto; i >= 1; i--) | |
| val[suffix[path[i]]] += val[path[i]]; | |
| } | |
| int main() | |
| { | |
| //FASTIO | |
| ///* | |
| #ifndef ONLINE_JUDGE | |
| freopen("in.txt", "r", stdin); | |
| freopen("out.txt", "w", stdout); | |
| freopen("error.txt", "w", stderr); | |
| #endif | |
| //*/ | |
| int T; | |
| scanf("%d", &T); | |
| //T = 1; | |
| //cin >> T; | |
| for (int cs = 1; cs <= T; cs++) { | |
| init(); | |
| int n; | |
| scanf("%d", &n); | |
| scanf("%s", s + 1); | |
| for (int i = 1; i <= n; i++) { | |
| scanf("%s", ch + 1); | |
| int l = strlen(ch + 1); | |
| makeTrie(i, l); | |
| } | |
| bfs(); | |
| int l = strlen(s + 1); | |
| search(l); | |
| printf("Case %d:\n", cs); | |
| for (int i = 1; i <= n; i++) { | |
| printf("%d\n", val[en[i]]); | |
| } | |
| } | |
| return 0; | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| using namespace std; | |
| #define INF 1<<30 | |
| #define endl '\n' | |
| #define maxn 100005 | |
| #define tc printf("Case %d: ", cs) | |
| #define tcn printf("Case %d:\n", cs); | |
| #define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); | |
| typedef long long ll; | |
| const double PI = acos(-1.0); | |
| #define dbg1(x) cerr << #x << " = " << x << endl; | |
| #define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl; | |
| #define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl; | |
| #define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl; | |
| const int N = 250004; | |
| const int M = 505; | |
| int n, name_of_node, cnt; | |
| int res[N]; | |
| int node[N][27]; | |
| int fail[N]; | |
| int path[N]; | |
| int end_node[N]; | |
| char txt[1000006], pat[M]; | |
| void init() | |
| { | |
| name_of_node = 0; | |
| cnt = 0; | |
| memset(path, 0, sizeof path); | |
| memset(fail, 0, sizeof fail); | |
| memset(res, 0, sizeof res); | |
| memset(node, -1, sizeof node); | |
| } | |
| void Insert(char s[], int pos) | |
| { | |
| int now = 0; | |
| int len = strlen(s); | |
| for (int i = 0; i < len; i++) { | |
| if (node[now][s[i] - 'a'] == -1) { | |
| node[now][s[i] - 'a'] = ++name_of_node; | |
| } | |
| now = node[now][s[i] - 'a']; | |
| } | |
| end_node[pos] = now; | |
| } | |
| void failure() | |
| { | |
| queue<int> Q; | |
| for (int i = 0; i < 26; i++) { | |
| if (~node[0][i]) | |
| Q.push(node[0][i]); | |
| else node[0][i] = 0; | |
| } | |
| while (!Q.empty()) { | |
| int u = Q.front(); | |
| Q.pop(); | |
| for (int i = 0; i < 26; i++) { | |
| int v = node[u][i]; | |
| if (~v) { | |
| Q.push(v); | |
| fail[v] = node[fail[u]][i]; | |
| path[++cnt] = v; | |
| } | |
| else { | |
| node[u][i] = node[fail[u]][i]; | |
| } | |
| } | |
| } | |
| return; | |
| } | |
| void aho_corasick(char s[]) | |
| { | |
| int now = 0; | |
| int len = strlen(s); | |
| for (int i = 0; i < len; i++) { | |
| now = node[now][s[i] - 'a']; | |
| res[now]++; | |
| } | |
| for (int i = cnt; i >= 1; i--) { | |
| res[fail[path[i]]] += res[path[i]]; | |
| } | |
| } | |
| int main() | |
| { | |
| FASTIO | |
| ///* | |
| #ifndef ONLINE_JUDGE | |
| freopen("in.txt", "r", stdin); | |
| freopen("out.txt", "w", stdout); | |
| freopen("error.txt", "w", stderr); | |
| #endif | |
| //*/ | |
| int T; | |
| scanf("%d", &T); | |
| //T = 1; | |
| for (int cs = 1; cs <= T; cs++) { | |
| init(); | |
| scanf("%d", &n); | |
| scanf("%s", txt); | |
| for (int i = 0; i < n; i++) { | |
| scanf("%s", pat); | |
| Insert(pat, i); | |
| } | |
| failure(); | |
| aho_corasick(txt); | |
| printf("Case %d:\n", cs); | |
| for (int i = 0; i < n; i++) { | |
| printf("%d\n", res[end_node[i]]); | |
| } | |
| } | |
| return 0; | |
| } |
No comments:
Post a Comment