daily pastebin goal
28%
SHARE
TWEET

Untitled

a guest Mar 23rd, 2019 65 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdio>
  2. #include <queue>
  3. #include <cstring>
  4. #include <bitset>
  5. #include <iostream>
  6.  
  7. using namespace std;
  8.  
  9. const int MAXR = 105;
  10. const int MAXN = 5005;
  11. const int MAXL = 30;
  12. const int MAXK = 4;
  13.  
  14. struct Trie
  15. {
  16.     //int iEnd;
  17.     int iEnd;
  18.     //vector <int> v;
  19.     int mask[MAXK];
  20.     Trie* child[MAXL];
  21.     Trie* nv, *openLink;
  22. };
  23.  
  24. void init(Trie* &temp)
  25. {
  26.     //printf("DSA");
  27.     temp = new Trie();
  28.     temp->iEnd = -1;
  29.     for(int i = 0; i < MAXL; i++)
  30.     {
  31.         temp->child[i] = nullptr;
  32.     }
  33.     temp->nv = nullptr; temp->openLink = nullptr;
  34. }
  35.  
  36. Trie* root;
  37. int n, m, r, c;
  38. char str1[MAXR][MAXR];
  39. char str2[MAXN][MAXN];
  40.  
  41. void add_word(Trie* &tree, int num, int f, int temp)
  42. {
  43.     //printf("%d %d\n", str1[temp][f], num);
  44.     if(temp == r)
  45.     {
  46.         //if(tree->iEnd == -1)
  47.         //tree->v.push_back(num);
  48.         int mask = num / 30;
  49.         int pos = num % 30;
  50.         tree->mask[mask] |= (1 << pos);
  51.         //printf("DSA");
  52.         tree->iEnd = num;
  53.         //tree->iEnd = num;
  54.     }
  55.     else
  56.     {
  57.         //printf("DSA");
  58.         //printf("%d\n", t[0]);
  59.         if(tree->child[str1[temp][f]] == nullptr)
  60.         {
  61.             init(tree->child[str1[temp][f]]);
  62.         }
  63.         add_word(tree->child[str1[temp][f]], num, f, temp + 1);
  64.     }
  65. }
  66.  
  67. void read_input()
  68. {
  69.     scanf("%d %d", &r, &c);
  70.  
  71.     for(int i = 0; i < r; i++)
  72.     {
  73.         scanf("%s", str1[i]);
  74.     }
  75.     for(int i = 0; i < r; i++)
  76.     {
  77.         for(int j = 0; j < c; j++)
  78.         {
  79.             str1[i][j] -= 'a';
  80.         }
  81.     }
  82.     //printf("DSA");
  83.     init(root);
  84.     for(int i = 0; i < c; i++)
  85.     {
  86.         add_word(root, i, i, 0);
  87.     }
  88.  
  89.     scanf("%d %d", &n, &m);
  90.     for(int i = 0; i < n; i++)
  91.     {
  92.         scanf("%s", str2[i]);
  93.     }
  94.     for(int i = 0; i < n; i++)
  95.     {
  96.         for(int j = 0; j < m; j++)
  97.         {
  98.             str2[i][j] -= 'a';
  99.         }
  100.     }
  101. }
  102.  
  103. void pre_links()
  104. {
  105.     queue <Trie*> q;
  106.  
  107.     root->nv = root;
  108.  
  109.     for(int i = 0; i < MAXL; i++)
  110.     {
  111.         if(root->child[i] != nullptr)
  112.         {
  113.             root->child[i]->nv = root;
  114.             q.push(root->child[i]);
  115.         }
  116.     }
  117.  
  118.     while(!q.empty())
  119.     {
  120.         Trie* v = q.front(); q.pop();
  121.  
  122.         for(int x = 0; x < MAXL; x++)
  123.         {
  124.             if(v->child[x] != nullptr)
  125.             {
  126.                 Trie* w = v->child[x];
  127.                 q.push(w);
  128.                 Trie* vw = v->nv;
  129.  
  130.                 while(vw->child[x] == nullptr && vw != root)
  131.                 {
  132.                     vw = vw->nv;
  133.                 }
  134.                 if(vw->child[x] != nullptr)
  135.                 {
  136.                     w->nv = vw->child[x];
  137.                 }
  138.                 else
  139.                 {
  140.                     w->nv = root;
  141.                 }
  142.                 if(w->nv->iEnd != -1)
  143.                 {
  144.                     w->openLink = w->nv;
  145.                 }
  146.                 else if(w->nv->openLink != nullptr)
  147.                 {
  148.                     w->openLink = w->nv->openLink;
  149.                 }
  150.             }
  151.         }
  152.     }
  153. }
  154.  
  155. int ans;
  156. int o;
  157. int current[2][MAXN][MAXK];
  158.  
  159. void report_end(int masks[MAXK], int row)
  160. {
  161.     int temp = (current[o ^ 1][row][0] << 1) & masks[0];
  162.     current[o][row][0] |= temp;
  163.     for(int i = 0; i < MAXK; i++)
  164.     {
  165.         temp = (current[o ^ 1][row][i] << 1) & masks[i];
  166.         current[o][row][i] |= temp;
  167.  
  168.         if(current[o ^ 1][row][i - 1] & (1 << 29))
  169.         {
  170.             current[o][row][i] |= 1;
  171.         }
  172.     }
  173.  
  174.     //printf("%d %d\n", masks[0], row);
  175.     //cout << bitset<2>(current[o ^ 1][row][0]) << "\n";
  176.  
  177.     int mask = (c - 1) / 30;
  178.     int pos = (c - 1) % 30;
  179.     //printf("%d\n", current[o][row][2]);
  180.     if(current[o][row][mask] & (1 << pos))
  181.     {
  182.         ans++;
  183.     }
  184.     if(masks[0] & 1)
  185.     {
  186.         //printf("DSA\n");
  187.         current[o][row][0] |= 1;
  188.     }
  189.     //printf("%d %d %d\n", nd, temp, row);
  190.     /*int z = 5;
  191.     for(int i = z - 1; i >= 0; i--)
  192.     {
  193.         //printf("%d\n", z);
  194.         int nd = 5;
  195.         if(nd == 0)
  196.         {
  197.             //printf("%d %d %d\n", nd, row, temp);
  198.             current[row][nd] = temp;
  199.             if(nd == c - 1)
  200.             {
  201.                 ans++;
  202.             }
  203.         }
  204.         int prev = current[row][nd - 1];
  205.         //printf("%d %d %d %d\n", nd, row, temp, prev);
  206.         if(temp - prev == 1 && prev != -1)
  207.         {
  208.             if(nd == c - 1)
  209.             {
  210.                 ans++;
  211.             }
  212.             current[row][nd] = temp;
  213.         }
  214.     }*/
  215. }
  216.  
  217. void full_ac(int coll)
  218. {
  219.     int i = 0;
  220.     Trie* w = root;
  221.     Trie* w1;
  222.     do
  223.     {
  224.         w1 = w->child[str2[i][coll]];
  225.  
  226.         while(w1 != nullptr)
  227.         {
  228.             if(w1->iEnd != -1)
  229.             {
  230.                 report_end(w1->mask, i);
  231.             }
  232.             if(w1->openLink != nullptr)
  233.             {
  234.                 if(w1->openLink->iEnd != -1)
  235.                 {
  236.                     report_end(w1->openLink->mask, i);
  237.                 }
  238.             }
  239.  
  240.             w = w1;
  241.             i++;
  242.             if(i >= n)
  243.             {
  244.                 break;
  245.             }
  246.  
  247.             w1 = w->child[str2[i][coll]];
  248.         }
  249.  
  250.         if(w != root)
  251.         {
  252.             w = w->nv;
  253.         }
  254.         else
  255.         {
  256.             i++;
  257.         }
  258.     }while(i < n);
  259. }
  260.  
  261. bool temp[MAXR];
  262.  
  263. void solve()
  264. {
  265.     //memset(current, -1, sizeof(current));
  266.     for(int i = 0; i < m; i++)
  267.     {
  268.         full_ac(i);
  269.         for(int j = 0; j < n; j++)
  270.         {
  271.             for(int z = 0; z < MAXK; z++)
  272.             {
  273.                 current[o ^ 1][j][z] = 0;
  274.             }
  275.         }
  276.         o ^= 1;
  277.     }
  278.     printf("%d\n", ans);
  279. }
  280.  
  281. int main()
  282. {
  283.     read_input();
  284.     pre_links();
  285.     solve();
  286.  
  287.     return 0;
  288. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top