Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <queue>
- #include <cstdlib>
- #include <cstring>
- #include <cmath>
- #include <algorithm>
- #include <string>
- #include <climits>
- #include <vector>
- #include <deque>
- #include <set>
- #include <map>
- #include <list>
- #include <stack>
- #include <cctype>
- #include <bitset>
- #include <ctime>
- #include <cassert>
- #include <fstream>
- #include <complex>
- #include <iomanip>
- using namespace std;
- #define MIN(x,y) (((x)<(y))?(x):(y))
- #define MAX(x,y) (((x)>(y))?(x):(y))
- #define ABS(x) (((x)<0)?(-(x)):(x))
- #define ff first
- #define ss second
- #define ei else if
- #define mp make_pair
- #define pb push_back
- typedef long long ll;
- typedef unsigned long long ull;
- typedef long double ld;
- typedef pair<int,int> pii;
- typedef pair<int,pair<int,int> > piii;
- const ld EPS = 1e-7;
- const ld PI = 3.141592653589793;
- const int MAX_N = 1234, MAX_LEN = 2005, ALP = 260;
- int N;
- string STR;
- bitset<MAX_N> res;
- struct Node {
- bitset<MAX_N> out;
- map<char, int> go;
- int fail;
- int pred;
- char symb;
- } t[5000005];
- int sz = 0;
- inline void trie_add(const string& s, int idx) {
- int v = 0; char c;
- for(int i = 0; i < s.length(); ++i) {
- c = s[i];
- if(t[v].go.find(c) == t[v].go.end()) {
- t[v].go.insert(mp(c, ++sz));
- t[sz].symb = c;
- t[sz].pred = v;
- }
- v = t[v].go[c];
- }
- t[v].out[idx] = 1;
- }
- /*
- ushers
- 4
- he
- hers
- his
- she
- */
- inline void failure_bfs() {
- queue<int> Q;
- Q.push(0);
- int v, state;
- char c;
- while(!Q.empty()) {
- v = Q.front(); Q.pop();
- for(map<char, int>::iterator it = t[v].go.begin(); it != t[v].go.end(); ++it)
- Q.push(it->second);
- if(v == 0 or t[v].pred == 0) {
- t[v].fail = 0;
- continue;
- }
- c = t[v].symb;
- state = t[t[v].pred].fail;
- while(state != 0 and t[state].go.find(c) == t[state].go.end())
- state = t[state].fail;
- if(t[state].go.find(c) != t[state].go.end())
- state = t[state].go[c];
- t[v].fail = state;
- t[v].out |= t[state].out;
- }
- }
- inline void next_func() {
- int go_state; char c;
- for(int state = 0; state <= sz; ++state) {
- go_state = t[state].fail;
- for(map<char, int>::iterator it = t[go_state].go.begin(); it != t[go_state].go.end(); ++it) {
- c = it->first;
- if(t[state].go.find(c) == t[state].go.end())
- t[state].go[c] = t[go_state].go[c];
- }
- }
- }
- inline void build_aho_cor() {
- failure_bfs();
- next_func();
- }
- /*
- void print_out() {
- for(int i = 0; i <= sz; ++i) {
- cout << i << '\t';
- for(set<int>::iterator it = t[i].out.begin(); it != t[i].out.end(); ++it)
- cout << *it << ' ';
- cout << '\n';
- }
- }
- */
- inline void recognize() {
- int v = 0; char c;
- for(int i = 0; i < STR.length(); ++i) {
- c = STR[i];
- if(t[v].go.find(c) != t[v].go.end())
- v = t[v].go[c];
- else
- v = 0;
- res |= t[v].out;
- }
- }
- inline void print_res() {
- for(int i = 0; i < N; ++i) {
- if(res[i] == 1)
- putchar('Y');
- else
- putchar('N');
- putchar('\n');
- }
- }
- bool solve() {
- while(cin >> STR) {
- cin >> N;
- string s;
- for(int i = 0; i < N; ++i) {
- cin >> s;
- trie_add(s, i);
- }
- build_aho_cor();
- // print_out();
- recognize();
- print_res();
- return true;
- }
- return false;
- }
- int main() {
- ios_base::sync_with_stdio(0);
- while(solve());
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement