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_M = 100100;
  36. const int MAX_N = 1100;
  37. const int MAX_WORD = 1100;
  38. const int MAX_AHO = 800100;
  39. const int MAX_LETTERS = 63;
  40. const int REDUCTION = 1;
  41.  
  42. char M[MAX_M];
  43.  
  44. int N;
  45.  
  46. bool isPresent[MAX_N];
  47. vector<int> repeats[MAX_N];
  48.  
  49. int lett(char c)
  50. {
  51.     if('a' <= c && c <= 'z') return 1+c-'a';
  52.     else if('A' <= c && c <= 'Z') return 1+26+c-'A';
  53.     else return 1+52+c-'0';
  54. }
  55.  
  56. struct node
  57. {
  58.     int val;
  59.  
  60.     int terminal;
  61.  
  62.     int parent;
  63.     int children[MAX_LETTERS];
  64.  
  65.     int fail;
  66.  
  67.     node()
  68.     {
  69.         val = 0;
  70.         terminal = 0;
  71.         parent = 0;
  72.         memset(children, 0, sizeof(children));
  73.         fail = 0;
  74.     }
  75. };
  76.  
  77. node aho[MAX_AHO/REDUCTION]; int sz;
  78.  
  79. char curWord[MAX_WORD]; int cwIdx;
  80. void add_word()
  81. {
  82.     int wLen = strlen(curWord);
  83.  
  84.     int idx = 1, pos = 0;
  85.     while(true)
  86.     {
  87.         if(pos == wLen)
  88.         {
  89.             if(aho[idx].terminal == 0) aho[idx].terminal = cwIdx++;
  90.             else repeats[aho[idx].terminal].push_back(cwIdx++);
  91.  
  92.             break;
  93.         }else if(aho[idx].children[lett(curWord[pos])] != 0) idx = aho[idx].children[lett(curWord[pos])];
  94.         else
  95.         {
  96.             aho[idx].children[lett(curWord[pos])] = sz;
  97.             aho[sz].val = lett(curWord[pos]);
  98.             aho[sz].parent = idx;
  99.  
  100.             idx = sz++;
  101.         }
  102.  
  103.         ++pos;
  104.     }
  105. }
  106.  
  107. int fail(int idx, int val)
  108. {
  109.     while(true)
  110.     {
  111.         if(aho[idx].children[val] != 0) return aho[idx].children[val];
  112.         else if(idx == 1) return 1;
  113.         idx = aho[idx].fail;
  114.     }
  115. }
  116.  
  117. void build_fails()
  118. {
  119.     queue<int> q;
  120.     q.push(1);
  121.  
  122.     while(!q.empty())
  123.     {
  124.         int u = q.front();
  125.         q.pop();
  126.  
  127.         for(int i = 0; i < MAX_LETTERS; i++)
  128.             if(aho[u].children[i] != 0)
  129.             {
  130.                 if(u == 1) aho[aho[u].children[i]].fail = 1;
  131.                 else aho[aho[u].children[i]].fail = fail(aho[u].fail, i);
  132.  
  133.                 q.push(aho[u].children[i]);
  134.             }
  135.     }
  136. }
  137.  
  138. int main (int argc, const char * argv[])
  139. {
  140.     scanf("%s", M);
  141.     scanf("%d", &N);
  142.  
  143.     int mLen = strlen(M);
  144.     for(int r = 1; r <= REDUCTION; r++)
  145.     {
  146.         memset(isPresent, 0, sizeof(isPresent));
  147.         for(int i = 0; i < MAX_N; i++)
  148.             repeats[i].clear();
  149.         memset(aho, 0, sizeof(aho));
  150.         sz = 2;
  151.         cwIdx = 1;
  152.  
  153.         for(int i = N*(r-1)/REDUCTION; i < N*r/REDUCTION; i++)
  154.         {
  155.             scanf("%s", curWord);
  156.  
  157.             add_word();
  158.         }
  159.  
  160.         build_fails();
  161.  
  162.         for(int i = 0, idx = 1; i < mLen; i++)
  163.         {
  164.             idx = fail(idx, lett(M[i]));
  165.  
  166.             int curIdx = idx;
  167.             while(aho[curIdx].terminal != 0)
  168.             {
  169.                 isPresent[aho[curIdx].terminal] = true;
  170.                 aho[curIdx].terminal = 0;
  171.                 curIdx = aho[curIdx].fail;
  172.             }
  173.         }
  174.  
  175.         for(int i = 1; i <= (N*r/REDUCTION)-N*(r-1)/REDUCTION; i++)
  176.             for(int j = 0; j < sz(repeats[i]); j++)
  177.                 isPresent[repeats[i][j]] = true;
  178.  
  179.         for(int i = 1; i <= (N*r/REDUCTION)-N*(r-1)/REDUCTION; i++)
  180.             if(isPresent[i]) cout << "Y\n";
  181.             else cout << "N\n";
  182.     }
  183.  
  184.     return 0;
  185. }
  186.  
Success #stdin #stdout 0.21s 212992KB
comments (?)
stdin
copy 
abghABCDE
2
abAB
ab
stdout
copy 
N
Y
https://ideone.com/ndQcN4
language:
C++ (gcc 8.3)
created:
10 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!