Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- struct Node{
- map<char,int> to;
- string s;
- int freq;
- int maxi;
- Node(string ss=""){s = ss;freq=0;}
- };
- typedef pair<int,int> ii;
- vector<Node> adj;
- int nn;
- void addToTrie(string ss){
- int pos = 0, len = ss.size(), u = 0;
- while(pos < len){
- if(adj[u].to[ss[pos]] == 0) break;
- adj[u].maxi = max(adj[u].maxi, len);
- u = adj[u].to[ss[pos]];
- adj[u].freq++;
- pos++;
- }
- while(pos < len){
- adj[u].to[ss[pos]] = ++nn;
- adj.push_back(Node(adj[u].s + ss[pos]));
- u = nn;
- adj[u].maxi = len;
- pos++;
- }
- }
- ii solve(string s){
- int pos = 0, len = s.size(), u = 0;
- while(pos < len){
- if(adj[u].to[s[pos]] == 0) return ii(-1,-1);
- u = adj[u].to[s[pos]];
- adj[u].freq++;
- pos++;
- }
- int freq = adj[u].freq;
- int maxi = adj[u].maxi;
- return ii(freq, maxi);
- }
- int main(){
- int t,q;
- string s;
- cin >> t;
- adj.push_back(Node());
- for(int i = 0; i < t; i++){
- cin >> s;
- addToTrie(s);
- }
- cin >> q;
- for(int i = 0; i < q; i++){
- cin >> s;
- ii res = solve(s);
- if(res.first == -1) printf("-1\n");
- else printf("%d %d\n",res.first, res.second);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement