fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define mp make_pair
  4. #define pb push_back
  5. #define s second
  6. #define f first
  7. struct trie
  8. {
  9.   unordered_map<char,trie*>alpha;
  10.   vector<int>str_num;
  11. };
  12. int main() {
  13. 	trie* head=new trie(); 
  14. 	int n;
  15. 	cin>>n;
  16. 	string str[n];
  17. 	for(int i=0;i<n;i++)
  18. 	cin>>str[i];
  19. 	trie *ptr=NULL;
  20. 	for(int i=0;i<n;i++)
  21. 	{
  22. 		ptr=head;
  23. 		for(int j=0;j<str[i].length();j++)
  24. 		{
  25. 			if(ptr->alpha.find(str[i][j])==ptr->alpha.end())
  26. 			{
  27. 				trie* node=new trie();
  28. 				if((node->str_num).size()==0)
  29. 				(node->str_num).pb(i);
  30. 				ptr->alpha[str[i][j]]=node;
  31. 				ptr=node;
  32. 			}
  33. 			else{
  34. 				ptr=ptr->alpha[str[i][j]];
  35. 				if(str[(ptr->str_num)[(ptr->str_num).size()-1]]>str[i])
  36. 					{
  37. 						(ptr->str_num).pb(i);
  38. 					}
  39. 			}
  40. 		}
  41. 	}
  42. 	int q;
  43. 	cin>>q;
  44. 	while(q--)
  45. 	{
  46. 		ptr=head;
  47. 		int r;
  48. 		string str1;
  49. 		cin>>r;
  50. 		cin>>str1;
  51. 		r--;
  52. 		int mmp=-1;
  53. 		for(int i=0;i<str1.length();i++)
  54. 		{
  55. 			if(ptr->alpha.find(str1[i])!=(ptr->alpha.end()))
  56. 			{
  57. 				ptr=ptr->alpha[str1[i]];
  58. 				vector<int>temp;
  59. 				temp=(ptr->str_num);
  60. 				for(int j=(temp).size()-1;j>=0;j--)
  61. 				{
  62. 					if(temp[j]<=r)
  63. 					{mmp=temp[j];
  64. 					break;}
  65. 				}
  66. 			}
  67. 			else break;
  68. 		}
  69. 		if(mmp!=-1)
  70. 		cout<<str[mmp];
  71. 		else cout<<str[0];
  72. 		cout<<endl;
  73. 	}
  74. 	return 0;
  75. }
Runtime error #stdin #stdout 0.09s 4256KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy
https://ideone.com/eFFVqJ
language:
C++14 (gcc 8.3)
created:
5 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!