fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct node {
  5. 	int to[26];
  6. 	int cnt;
  7. 	node() {
  8. 		memset (to, 0, sizeof to);
  9. 		cnt = 0;
  10. 	}
  11. };
  12. vector<node> t(1);
  13. map<string, int> ans;
  14. int go (string s, bool add) {
  15. 	int v = 0;
  16. 	int sum = 0;
  17. 	for (int i = 0; i < s.size(); i++) {
  18.  
  19. 		int c = s[i] - 'a';
  20. 		if (!t[v].to[c]) {
  21. 			t[v].to[c] = t.size();
  22. 			t.push_back(node());
  23. 		}
  24. 		v = t[v].to[c];
  25. 		sum += t[v].cnt;
  26. 		if (add)
  27. 			t[v].cnt++;
  28. 	}
  29. 	return sum;
  30. }
  31. int main() {
  32. 	int n;
  33. 	cin >> n;
  34. 	for (int i = 1; i <= n; i++) {
  35. 		string s;
  36. 		cin >> s;
  37. 		int v = go(s, 1);
  38. 		if (!ans.count(s))
  39. 			ans[s] = v + s.length()+i;
  40.  
  41. 		//cout << ans[s] << endl;
  42. 	}
  43. 	int q;
  44. 	cin >> q;
  45. 	while (q--) {
  46. 		string s;
  47. 		cin >> s;
  48. 		if (ans.count (s))
  49. 			cout<< ans[s]<<endl;
  50. 		else
  51. 		{
  52. 			cout << go(s, 0) + n << endl;
  53. 		}
  54. 	}
  55. 	return 0;
  56. }
Success #stdin #stdout 0s 5296KB
comments (?)
stdin
copy 
3
ba
ab
abc
3
a
ba
ab
stdout
copy 
5
3
4
https://ideone.com/suqU9r
3
ba
ab
abc
3
cd
ba
ab
language:
C++14 (gcc 8.3)
created:
6 days 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!