Advertisement
Guest User

Untitled

a guest
Sep 23rd, 2017
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.33 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct Node{
  6.     map<char,int> to;
  7.     string s;
  8.     int freq;
  9.     int maxi;
  10.     Node(string ss=""){s = ss;freq=0;}
  11. };
  12. typedef pair<int,int> ii;
  13. vector<Node> adj;
  14.  
  15. int nn;
  16.  
  17. void addToTrie(string ss){
  18.     int pos = 0, len = ss.size(), u = 0;
  19.     while(pos < len){
  20.         if(adj[u].to[ss[pos]] == 0) break;
  21.         adj[u].maxi = max(adj[u].maxi, len);
  22.         u = adj[u].to[ss[pos]];
  23.         adj[u].freq++;
  24.         pos++;
  25.     }
  26.     while(pos < len){
  27.         adj[u].to[ss[pos]] = ++nn;
  28.         adj.push_back(Node(adj[u].s + ss[pos]));
  29.         u = nn;
  30.         adj[u].maxi = len;
  31.         pos++;
  32.     }
  33. }
  34.  
  35. ii solve(string s){
  36.     int pos = 0, len = s.size(), u = 0;
  37.     while(pos < len){
  38.         if(adj[u].to[s[pos]] == 0) return ii(-1,-1);
  39.         u = adj[u].to[s[pos]];
  40.         adj[u].freq++;
  41.         pos++;
  42.     }
  43.     int freq = adj[u].freq;
  44.     int maxi = adj[u].maxi;
  45.     return ii(freq, maxi);
  46. }
  47.  
  48. int main(){
  49.     int t,q;
  50.     string s;
  51.  
  52.     cin >> t;
  53.     adj.push_back(Node());
  54.     for(int i = 0; i < t; i++){
  55.         cin >> s;
  56.         addToTrie(s);
  57.     }
  58.  
  59.     cin >> q;
  60.     for(int i = 0; i < q; i++){
  61.         cin >> s;
  62.         ii res = solve(s);
  63.         if(res.first == -1) printf("-1\n");
  64.         else printf("%d %d\n",res.first, res.second);
  65.     }
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement