fork(5) download
copy 
  1. #include <algorithm>
  2. #include <cmath>
  3. #include <cstdio>
  4. #include <deque>
  5. #include <iomanip>
  6. #include <iostream>
  7. #include <map>
  8. #include <queue>
  9. #include <set>
  10. #include <stack>
  11. #include <stdlib.h>
  12. #include <string>
  13. #include <vector>
  14.  
  15. using namespace std;
  16.  
  17. #define LL long long
  18. #define LD long double
  19.  
  20. #define VI vector<int>
  21.  
  22. #define PB push_back
  23. #define MP make_pair
  24. #define F first
  25. #define S second
  26. #define PII pair<int,int>
  27. #define PPII pair< PI , PI >
  28.  
  29. #define INF 2000000009
  30.  
  31. #if 0
  32. #define get getchar_unlocked
  33. #else
  34. #define get getchar
  35. #endif
  36.  
  37. /* Main Code */
  38.  
  39. #define MAXW 501
  40. #define MAXN 101
  41. #define MAXPL 5001
  42. #define MAXSL 50001
  43. #define MAXNODES 26000
  44. #define MAXC 64
  45.  
  46. string P[MAXW],S[MAXN];
  47. int w,n;
  48. char inp[MAXPL],ins[MAXSL],node_ch[MAXNODES];
  49. int ans[MAXW] = {0},node[MAXNODES][MAXC],lsp[MAXNODES],matches[MAXNODES] = {0},parent[MAXNODES];
  50. int i,j,var,sz,k,pnn;
  51. vector<int> node_p[MAXNODES];
  52. vector<PII> new_node;
  53.  
  54. string ip,is;
  55.  
  56. inline void TakeInput(){
  57. #if 1
  58.     cin>>w;
  59.     for(i = 0;i < w;i++){
  60.         cin>>P[i];
  61.     }
  62.     cin>>n;
  63.     for(i = 0;i < n;i++){
  64.         cin>>S[i];
  65.     }
  66. #else
  67.     w = 500;
  68.     ip = "";
  69.     for(i = 0;i < 5000;i++){
  70.         ip += "a";
  71.     }
  72.     for(i = 0;i < w;i++){
  73.         P[i] = ip;
  74.     }
  75.     n = 100;
  76.     is = "";
  77.     for(i = 0;i < 50000;i++){
  78.         is += "a";
  79.     }
  80.     for(i = 0;i < n;i++){
  81.         S[i] = is;
  82.     }
  83. #endif
  84. }
  85.  
  86. inline int Index(char ch){
  87. #if 1
  88.     if((ch >= 'a') && (ch <= 'z')){
  89.         return ch - 'a';
  90.     }
  91.     else if((ch >= 'A') && (ch <= 'Z')){
  92.         return ch - 'A' + 26;
  93.     }
  94.     else if((ch >= '0') &&(ch <= '9')){
  95.         return ch - '0' + 52;
  96.     }
  97.     else if(ch == '-'){
  98.         return 62;
  99.     }
  100.     else {
  101.         return 63;
  102.     }
  103. #else
  104.     return (int)ch;
  105. #endif
  106. }
  107.  
  108. inline void AddStringToAutomaton(int i){
  109.     var = 0;
  110.     j = 0;
  111.     sz = P[i].length();
  112.     while(j < sz){
  113.         k = Index(P[i][j]);
  114.         if(node[var][k] == -1){
  115.             pnn++;
  116.             node[var][k] = pnn;
  117.             node_ch[pnn] = P[i][j];
  118.             parent[pnn] = var;
  119.         }
  120.         var = node[var][k];
  121.         j++;
  122.     }
  123.     node_p[var].PB(i);
  124. }
  125.  
  126. inline void PrepareAutomaton(){
  127.     pnn = 0;
  128.     for(i = 0;i < MAXNODES;i++){
  129.         for(j = 0;j < MAXC;j++){
  130.             node[i][j] = -1;
  131.         }
  132.     }
  133.     for(i = 0;i < w;i++){
  134.         AddStringToAutomaton(i);
  135.     }
  136.     lsp[0] = 0;
  137.     for(i = 1;i <= pnn;i++){
  138.         j = lsp[parent[i]];
  139.         k = Index(node_ch[i]);
  140.         while(j > 0){
  141.             if(node[j][k] != -1){
  142.                 j = node[j][k];
  143.                 break;
  144.             }
  145.             j = lsp[j];
  146.         }
  147.         if((parent[i] != 0) && (j == 0)){
  148.             if(node[0][k] != -1){
  149.                 j = node[0][k];
  150.             }
  151.         }
  152.         lsp[i] = j;
  153.     }
  154.     /*
  155.     for(i = 1;i <= pnn;i++){
  156.         cout<<i<<" "<<node_ch[i]<<" "<<parent[i]<<" "<<node_ch[parent[i]]<<" "<<lsp[i]<<" "<<node[0][Index(node_ch[i])]<<endl;
  157.     }
  158.     for(i = 1;i <= pnn;i++){
  159.         cout<<i<<" : ";
  160.         for(j = 0;j < node_p[i].size();j++){
  161.             cout<<node_p[i][j]<<" ";
  162.         }
  163.         cout<<endl;
  164.     }
  165.     //*/
  166. }
  167.  
  168. inline void Process(int i){
  169.     int j,k,l,m;
  170.     l = S[i].length();
  171.     var = 0;
  172.     for(j = 0;j < l;j++){
  173.         k = Index(S[i][j]);
  174.         while(var > 0){
  175.             if(node[var][k] != -1){
  176.                 var = node[var][k];
  177.                 break;
  178.             }
  179.             //cout<<i<<" : "<<j<<" "<<var<<" "<<lsp[var]<<endl;
  180.             var = lsp[var];
  181.         }
  182.         if(var == 0){
  183.             if(node[0][k] != -1){
  184.                 var = node[0][k];
  185.             }
  186.         }
  187.         matches[var]++;
  188.         //cout<<i<<" "<<j<<" "<<S[i][j]<<" "<<var<<endl;
  189.     }
  190. }
  191.  
  192. inline void Solve(){
  193.     int i;
  194.     for(i = 0;i < n;i++){
  195.         Process(i);
  196.     }
  197.     /*
  198.     for(i = 1;i <= pnn;i++){
  199.         cout<<i<<" "<<matches[i]<<endl;
  200.     }
  201.     cout<<endl;
  202.     //*/
  203.     new_node.PB(MP(0,0));
  204.     for(i = 1;i <= pnn;i++){
  205.         j = new_node[parent[i]].F + 1;
  206.         new_node.PB(MP(j,i));
  207.     }
  208.     sort(new_node.begin(),new_node.end());
  209.     for(i = pnn;i > 0;i--){
  210.         k = new_node[i].S;
  211.         matches[lsp[k]] += matches[k];
  212.         for(j = node_p[k].size() - 1;j >= 0;j--){
  213.             ans[node_p[k][j]] = matches[k];
  214.         }
  215.     }
  216.     for(i = 0;i < w;i++){
  217.         cout<<ans[i]<<endl;
  218.     }
  219. }
  220.  
  221. int main(){
  222.     TakeInput();
  223.     PrepareAutomaton();
  224.     Solve();
  225.     return 0;
  226. }
Success #stdin #stdout 0s 10632KB
comments (?)
stdin
copy 
2
ab
cab
1
acabbab
stdout
copy 
2
1
https://ideone.com/ZAIpye
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

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!