fork(1) download
copy 
  1. // iostream is too mainstream
  2. #include <cstdio>
  3. // bitch please
  4. #include <iostream>
  5. #include <vector>
  6. #include <set>
  7. #include <map>
  8. #include <string>
  9. #include <queue>
  10. #include <stack>
  11. #include <algorithm>
  12. #include <iomanip>
  13. #define dibs reserve
  14. #define OVER9000 1234567890
  15. #define patkan 9
  16. #define tisic 47
  17. #define soclose 10e-7
  18. #define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
  19. #define chocolate win
  20. #define ff first
  21. #define ss second
  22. #define abs(x) ((x < 0)?-(x):(x))
  23. // mylittlepony
  24. using namespace std;
  25.  
  26. struct node {
  27. 	int son[26];
  28. 	int sum;
  29. 	};
  30.  
  31. struct trie {
  32. 	vector<node> T;
  33. 	int t;
  34. 	node n0;
  35.  
  36. 	trie() {
  37. 		n0.sum =0;
  38. 		for(int i =0; i < 26; i++) n0.son[i] =-1;
  39. 		T.resize(1000000,n0);
  40. 		t =1;}
  41.  
  42. 	void put(string &s) {
  43. 		int L =s.length(), akt =0;
  44. 		for(int i =0; i < L; i++) {
  45. 			T[akt].sum++;
  46. 			if(T[akt].son[s[i]-'a'] == -1) T[akt].son[s[i]-'a'] =t++;
  47. 			akt =T[akt].son[s[i]-'a'];}
  48. 		T[akt].sum++;}
  49.  
  50. 	int get(string &s) {
  51. 		int L =s.length(), akt =0, ret =0;
  52. 		for(int i =0; i < L; i++) {
  53. 			ret +=T[akt].sum;
  54. 			if(T[akt].son[s[i]-'a'] == -1) break;
  55. 			akt =T[akt].son[s[i]-'a'];
  56. 			if(i == L-1) ret +=T[akt].sum;}
  57. 		return ret;}
  58. 	};
  59.  
  60. int main() {
  61.     cin.sync_with_stdio(0);
  62.     cin.tie(0);
  63.     int N,Q;
  64.     cin >> N;
  65.     map<string,int> M;
  66.     vector<string> A(N);
  67.     for(int i =0; i < N; i++) {
  68.     	string s;
  69.     	cin >> s;
  70.     	M[s] =i;
  71.     	A[i] =s;}
  72.  
  73.     cin >> Q;
  74.     vector<int> ans(Q);
  75.     vector<string> B(Q);
  76.     vector< vector<int> > query(N+1);
  77.     for(int i =0; i < Q; i++) {
  78.     	string s;
  79.     	cin >> s;
  80.     	B[i] =s;
  81.     	auto it =M.find(s);
  82.     	if(it == M.end()) query[N].push_back(i);
  83.     	else query[it->ss].push_back(i);}
  84.  
  85.     trie tr;
  86.     for(int i =0; i <= N; i++) {
  87.     	if(i < N) tr.put(A[i]);
  88.     	int b =(i == N)?0:tr.get(A[i]);
  89.     	ALL_THE(query[i],it) {
  90.     		if(i < N) ans[*it] =b;
  91.     		else ans[*it] =tr.get(B[*it]);}
  92.     	}
  93.  
  94.     for(int i =0; i < Q; i++) cout << ans[i] << "\n";
  95.    	return 0;}
  96.  
  97. // look at my code
  98. // my code is amazing
Success #stdin #stdout 0.11s 3440KB
comments (?)
stdin
copy 
8
majmunica
majmun
majka
malina
malinska
malo
maleni
malesnica
3
krampus
malnar
majmun
stdout
copy 
8
29
14
https://ideone.com/hZsvc5
CT S02E04 J
language:
C++14 (gcc 8.3)
created:
10 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!