fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int MaxN = 500500;
  6. int sz = 0;
  7.  
  8. struct node {
  9. 	int next[27];
  10. 	int HowManyStringsEndsAtThisVertex;
  11. 	node () {
  12. 		memset (next, 255, sizeof next);
  13. 	}
  14. } t[MaxN];
  15.  
  16. void insert (string &s) {
  17. 	int v = 0;
  18.  
  19. 	for (int i = 0; i < s.size(); ++i) {
  20. 	    int c = s[i] - 'a';
  21. 		if (t[v].next[c] == -1)
  22. 			t[v].next[c] = ++sz;
  23. 		v = t[v].next[c];
  24. 	}
  25. 	t[v].HowManyStringsEndsAtThisVertex++;
  26. }
  27.  
  28. bool search (string tmp) {
  29. 	int v = 0;
  30.  
  31. 	for (int i = 0; i < tmp.size(); ++i) {
  32. 		int c = tmp[i] - 'a';
  33. 		if (t[v].next[c] == -1)
  34. 			return false;
  35. 		v = t[v].next[c];
  36. 	}
  37. 	return t[v].HowManyStringsEndsAtThisVertex > 0;
  38. }
  39.  
  40. int main () {
  41. 	string keys[] = {"hi", "hello", "you", "ekta", "me"};
  42. 	string output[] = {"NO", "YES"};
  43.  
  44. 	for (int i = 0; i < 5; ++i)
  45. 		insert (keys[i]);
  46.  
  47. 	cout << output[search ("my")] << endl;
  48. 	cout << output[search ("me")] << endl;
  49.  
  50. 	return 0;
  51. }
  52.  
Success #stdin #stdout 0.04s 58176KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
NO
YES
https://ideone.com/fi22HK
language:
C++14 (gcc 8.3)
created:
9 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!