fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int maxn = 4e4;
  6. int len[maxn], link[maxn], cnt[maxn][2], used[maxn];
  7. map<char, int> to[maxn];
  8. int sz, last, ans;
  9.  
  10. void init(int n)
  11. {
  12.     for(int i = 0; i < sz; i++)
  13.     {
  14.         to[i].clear();
  15.         len[i] = link[i] = cnt[i][0] = cnt[i][2] = used[i] = 0;
  16.     }
  17.     link[0] = -1;
  18.     sz = 1, last = ans = 0;
  19. }
  20.  
  21. void add_letter(char c)
  22. {
  23.     int p = last;
  24.     last = sz++;
  25.     len[last] = len[p] + 1;
  26.     for(; p != -1 && !to[p][c]; p = link[p]) to[p][c] = last;
  27.     if(p == -1) return;
  28.     int q = to[p][c];
  29.     if(len[q] == len[p] + 1)
  30.     {
  31.         link[last] = q;
  32.         return;
  33.     }
  34.     int cl = sz++;
  35.     to[cl] = to[q];
  36.     link[cl] = link[q];
  37.     len[cl] = len[p] + 1;
  38.     link[last] = link[q] = cl;
  39.     for(; p != -1 && to[p][c] == q; p = link[p]) to[p][c] = cl;
  40. }
  41.  
  42. int dfs(int x, int k)
  43. {
  44.     if(used[x]) return ans;
  45.     used[x] = 1;
  46.     cnt[x][0] = cnt[x][1] = 0;
  47.     for(auto it: to[x])
  48.     {
  49.         if(it.first == '#')
  50.             cnt[x][0]++;
  51.         else if(it.first == '$')
  52.             cnt[x][1]++;
  53.         else
  54.         {
  55.             dfs(it.second, k);
  56.             cnt[x][0] += cnt[it.second][0];
  57.             cnt[x][1] += cnt[it.second][1];
  58.         }
  59.     }
  60.     if(x)
  61.         ans += (cnt[x][0] != 0) * (cnt[x][1] == k) * (len[x] - len[link[x]]);
  62.     return ans;
  63. }
  64.  
  65.  main()
  66.  {
  67.      ios::sync_with_stdio(0);
  68.      cin.tie(0);
  69.      int t;
  70.      cin >> t;
  71.      for(int i = 1; i <= t; i++)
  72.      {
  73.          string a, b;
  74.          cin >> a >> b;
  75.          init(a.size() + b.size() + 2);
  76.          for(auto c: a) add_letter(c);
  77.          add_letter('#');
  78.          for(auto c: b) add_letter(c);
  79.          add_letter('$');
  80.          int k;
  81.          cin >> k;
  82.          cout << "Case #" << i << ":\n" << dfs(0, k) << "\n";
  83.      }
  84.  }
  85.  
Success #stdin #stdout 0s 5152KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Case #1:
0
https://ideone.com/2bc3OA
http://w...content-available-to-author-only...j.com/ranks/STRSOCU/
language:
C++14 (gcc 8.3)
created:
9 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!