fork(1) download
copy 
  1. /***********Template Starts Here***********/
  2. #include <bits/stdc++.h>
  3.  
  4. #define pb push_back
  5. #define nl puts ("")
  6. #define sp printf ( " " )
  7. #define phl printf ( "hello\n" )
  8. #define ff first
  9. #define ss second
  10. #define POPCOUNT __builtin_popcountll
  11. #define RIGHTMOST __builtin_ctzll
  12. #define LEFTMOST(x) (63-__builtin_clzll((x)))
  13. #define MP make_pair
  14. #define FOR(i,x,y) for(vlong i = (x) ; i <= (y) ; ++i)
  15. #define ROF(i,x,y) for(vlong i = (y) ; i >= (x) ; --i)
  16. #define CLR(x,y) memset(x,y,sizeof(x))
  17. #define UNIQUE(V) (V).erase(unique((V).begin(),(V).end()),(V).end())
  18. #define MIN(a,b) ((a)<(b)?(a):(b))
  19. #define MAX(a,b) ((a)>(b)?(a):(b))
  20. #define NUMDIGIT(x,y) (((vlong)(log10((x))/log10((y))))+1)
  21. #define SQ(x) ((x)*(x))
  22. #define ABS(x) ((x)<0?-(x):(x))
  23. #define FABS(x) ((x)+eps<0?-(x):(x))
  24. #define ALL(x) (x).begin(),(x).end()
  25. #define LCM(x,y) (((x)/gcd((x),(y)))*(y))
  26. #define SZ(x) ((vlong)(x).size())
  27. #define NORM(x) if(x>=mod)x-=mod;
  28.  
  29. using namespace std;
  30.  
  31. typedef long long vlong;
  32.  
  33. /***********Template Ends Here***********/
  34. #define SIZE 6000000
  35. #define RSIZE 6000000
  36.  
  37. char buf[1010];
  38.  
  39. struct node {
  40.     int child[27];
  41.  
  42.     void clear () {
  43.         CLR(child,-1);
  44.     }
  45. }tnQ[SIZE+10], tnS[RSIZE+10];
  46. int freeIndexQ, freeIndexS;
  47.  
  48. void clearQ () {
  49.     freeIndexQ = 1;
  50.     tnQ[0].clear();
  51. }
  52. void clearS() {
  53.     freeIndexS = 1;
  54.     tnS[0].clear();
  55. }
  56.  
  57. int res[SIZE+10]; ///Okay
  58.  
  59. char luffy[100];
  60.  
  61. ///Inserts into the trie for query
  62. int insertQ ( ){
  63.     int cur = 0;
  64.     int len = strlen(luffy);
  65.  
  66.     FOR(i,0,len-1) {
  67.         char c = luffy[i];
  68.         if ( c == '#' ) c = 26; ///Okay
  69.         else c -= 'a';
  70.  
  71.         if ( tnQ[cur].child[c] == -1 ) { ///No child
  72.             tnQ[freeIndexQ].clear(); ///Clear it first
  73.             tnQ[cur].child[c] = freeIndexQ++;
  74.         }
  75.  
  76.         cur = tnQ[cur].child[c];
  77.     }
  78.     return cur;
  79. }
  80.  
  81. char zoro[100];
  82. ///Update each end of query string in query trie
  83. void queryQ ( ){
  84.     int cur = 0;
  85.     int len = strlen ( zoro );
  86.  
  87.     FOR(i,0,len-1) {
  88.         char c = zoro[i];
  89.         if ( c == '#' ) c = 26;
  90.         else c -= 'a';
  91.  
  92.         if ( tnQ[cur].child[c] == -1 ) {
  93.             return;
  94.         }
  95.         cur = tnQ[cur].child[c];
  96.     }
  97.     res[cur]++;
  98.  
  99. }
  100.  
  101. ///Create all possible query strings from unique substring
  102. void queryAll ( int st, int en ) {
  103.     int len = en - st;
  104.     int l = MIN(len,10);
  105.  
  106.     int zind = 0;
  107.     FOR(i,0,l-1){
  108.         zoro[zind++] = buf[st+i]; ///First put the prefix
  109.  
  110.         int nzind = zind; ///Now start a new index of suffix
  111.  
  112.         zoro[nzind++] = '#'; ///First of # to separate them
  113.         FOR(j,0,l-1){
  114.             zoro[nzind++] = buf[en-1-j];
  115.             zoro[nzind] = 0; ///A possible query is finished
  116.             queryQ();
  117.         }
  118.     }
  119. }
  120.  
  121. ///Insert suffix into second trie for main string
  122. void insertS ( int st, int len ){
  123.     int cur = 0;
  124.  
  125.     FOR(i,0,len-1) {
  126.         char c = buf[st+i];
  127.         c -= 'a';
  128.  
  129.         bool newNode = false;
  130.         if ( tnS[cur].child[c] == -1 ) {
  131.             tnS[freeIndexS].clear();
  132.             tnS[cur].child[c] = freeIndexS++;
  133.             newNode = true;
  134.         }
  135.  
  136.         cur = tnS[cur].child[c];
  137.  
  138.         if ( newNode ) { ///New node found
  139.             queryAll ( st, st+i+1 );
  140.         }
  141.     }
  142. }
  143.  
  144. char query[50010][25];
  145.  
  146. int main () {
  147.  
  148.     int kase, cnt = 0;
  149.     scanf ( "%d", &kase );
  150.  
  151.     while ( kase-- ) {
  152.         CLR(res,0); ///clear res to 0
  153.         clearQ(); ///Clear trie for query
  154.         clearS(); ///Clear trie for String
  155.  
  156.         scanf ( "%s", buf ); ///Take main string in buf
  157.  
  158.         int q;
  159.         scanf ( "%d", &q ); ///Number of query
  160.  
  161.         FOR(i,0,q-1) {
  162.             scanf ( "%s", luffy ); ///Take first string of in luffy
  163.  
  164.             int luf = 0;
  165.             luf = strlen ( luffy );
  166.  
  167.             luffy[luf] = '#'; ///Attach a # at end
  168.             luf++;
  169.  
  170.             scanf ( "%s", luffy + luf  ); ///take input from end of luffy
  171.             reverse ( luffy + luf, luffy + strlen ( luffy ) ); ///reverse as needed.
  172.  
  173.             insertQ ();
  174.  
  175.             strcpy ( &query[i][0], luffy ); ///Keep a copy of query to process later
  176.  
  177.         }
  178.  
  179.         int len = strlen ( buf );
  180.  
  181.         FOR(i,0,len-1) {
  182.             insertS( i, len - i ); ///Start and length
  183.         }
  184.  
  185.         printf ( "Case %d:\n", ++cnt );
  186.         FOR(i,0,q-1){
  187.             strcpy ( luffy, &query[i][0] );
  188.             int t = insertQ ( );
  189.             printf ( "%d\n", res[t] );
  190.         }
  191.     }
  192.  
  193.     return 0;
  194. }
  195.  
Runtime error #stdin #stdout 0s 148KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/fsYMxI
Blog UVa 12837 - Hasmot Ali Professor
language:
C++14 (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!