fork download
copy 
  1. //tonynater - SPOJ 2013
  2.  
  3. #include <algorithm>
  4. #include <bitset>
  5. #include <cassert>
  6. #include <cmath>
  7. #include <ctime>
  8. #include <fstream>
  9. #include <iomanip>
  10. #include <iostream>
  11. #include <list>
  12. #include <map>
  13. #include <queue>
  14. #include <set>
  15. #include <sstream>
  16. #include <stack>
  17. #include <string>
  18. #include <vector>
  19. #include <stdio.h>
  20. #include <stdlib.h>
  21. #include <string.h>
  22.  
  23. using namespace std;
  24.  
  25. #define sz(x) ((int) x.size())
  26.  
  27. typedef long double ld;
  28. typedef long long ll;
  29. typedef pair<int, int> pii;
  30.  
  31. const double pi = acos(-1);
  32. const double tau = 2*pi;
  33. const double epsilon = 1e-6;
  34.  
  35. const int MAX_N = 1100;
  36. const int MAX_AHO = 2000100;
  37.  
  38. string M;
  39.  
  40. int N;
  41.  
  42. bool isPresent[MAX_N];
  43. vector<int> repeats[MAX_N];
  44.  
  45. struct node
  46. {
  47.     int val;
  48.  
  49.     int terminal;
  50.  
  51.     int parent;
  52.     map<int, int> children;
  53.     int fail;
  54.  
  55.     node()
  56.     {
  57.         val = -1;
  58.         terminal = -1;
  59.         parent = -1;
  60.         children.clear();
  61.         fail = -1;
  62.     }
  63. };
  64.  
  65. node aho[MAX_AHO]; int sz = 1;
  66.  
  67. string curWord; int cwIdx;
  68. void add_word()
  69. {
  70.     int idx = 0, pos = 0;
  71.     while(true)
  72.     {
  73.         if(pos == sz(curWord))
  74.         {
  75.             if(aho[idx].terminal == -1) aho[idx].terminal = cwIdx++;
  76.             else repeats[aho[idx].terminal].push_back(cwIdx++);
  77.  
  78.             break;
  79.         }else if(aho[idx].children.count(curWord[pos]) > 0) idx = aho[idx].children[curWord[pos]];
  80.         else
  81.         {
  82.             aho[idx].children[curWord[pos]] = sz;
  83.             aho[sz].val = curWord[pos];
  84.             aho[sz].parent = idx;
  85.  
  86.             idx = sz++;
  87.         }
  88.  
  89.         ++pos;
  90.     }
  91. }
  92.  
  93. int fail(int idx, int val)
  94. {
  95.     while(true)
  96.         if(aho[idx].children.count(val) > 0) return aho[idx].children[val];
  97.         else if(idx == 0) return 0;
  98.         else idx = aho[idx].fail;
  99. }
  100.  
  101. void build_fails()
  102. {
  103.     queue<int> q;
  104.     q.push(0);
  105.  
  106.     while(!q.empty())
  107.     {
  108.         int u = q.front();
  109.         q.pop();
  110.  
  111.         for(map<int,int>::const_iterator it = aho[u].children.begin(); it != aho[u].children.end(); it++)
  112.         {
  113.             if(u == 0) aho[it->second].fail = 0;
  114.             else aho[it->second].fail = fail(aho[u].fail, it->first);
  115.  
  116.             q.push(it->second);
  117.         }
  118.     }
  119. }
  120.  
  121. int main (int argc, const char * argv[])
  122. {
  123.     ios_base::sync_with_stdio(0);
  124.     cin.tie(NULL);
  125.  
  126.     cin >> M >> N;
  127.  
  128.     for(int i = 0; i < N; i++)
  129.     {
  130.         cin >> curWord;
  131.  
  132.         add_word();
  133.     }
  134.  
  135.     build_fails();
  136.  
  137.     for(int i = 0, idx = 0; i < sz(M); i++)
  138.     {
  139.         idx = fail(idx, M[i]);
  140.  
  141.         int curIdx = idx;
  142.         while(aho[curIdx].terminal != -1)
  143.         {
  144.             isPresent[aho[curIdx].terminal] = true;
  145.             aho[curIdx].terminal = -1;
  146.             curIdx = aho[curIdx].fail;
  147.         }
  148.     }
  149.  
  150.     for(int i = 0; i < N; i++)
  151.         if(isPresent[i])
  152.             for(int j = 0; j < sz(repeats[i]); j++)
  153.                 isPresent[repeats[i][j]] = true;
  154.  
  155.     for(int i = 0; i < N; i++)
  156.         if(isPresent[i]) cout << "Y\n";
  157.         else cout << "N\n";
  158.  
  159.     return 0;
  160. }
  161.  
Success #stdin #stdout 0.1s 81600KB
comments (?)
stdin
copy 
abghABCDE
2
abAB
ab
stdout
copy 
N
Y
https://ideone.com/3P7XIj
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!