fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll int
  4. unordered_map<ll,ll>vis;
  5. unordered_map<ll,ll>trie[26];
  6. ll ans[100005];
  7. ll sz;
  8. void in(char s[])
  9. {
  10.     ll st=0,dep=0,mi=0;
  11.     for (ll i=0;i<strlen(s);i++)
  12.     {
  13.         dep+=1;
  14.         ll cur=s[i]-97;
  15.         if(!vis[trie[cur][st]])
  16.         {
  17.             trie[cur][st]=++sz;
  18.         }
  19.  
  20.         vis[trie[cur][st]]+=1;
  21.         if(i==0)
  22.             mi=vis[trie[cur][st]];
  23.         else
  24.         {
  25.           mi=min(mi,vis[trie[cur][st]]);
  26.         }
  27.         ans[dep]=max(ans[dep],mi);
  28.         st=trie[cur][st];
  29.     }
  30. }
  31.  
  32.  
  33. char s[100005];
  34. int main()
  35. {
  36.     ll i,j,k,n,m,t;
  37.     scanf("%d",&t);
  38.     while(t--)
  39.     {
  40.         ll q;
  41.         sz=0;
  42.         for(i=0;i<=100000;i++)
  43.         {
  44.             ans[i]=0;
  45.         }
  46.         for(i=0;i<26;i++) trie[i].clear();
  47.         vis.clear();
  48.         scanf("%d %d",&n,&q);
  49.         while(n--)
  50.         {
  51.             scanf("%s",s);
  52.             in(s);
  53.         }
  54.         while(q--)
  55.         {
  56.             scanf("%d",&j);
  57.             printf("%d\n",ans[j]);
  58.         }
  59.  
  60.     }
  61.  
  62. }
  63.  
Success #stdin #stdout 0s 4580KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/fNAWjb
language:
C++14 (clang 8.0)
created:
5 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!