fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. struct node {
  5.     int word;
  6.     node* edges[26];
  7. };
  8. node* get() {
  9.     node* x = new node;
  10.     x->word = -1;
  11.     for (int i = 0; i < 26; i++) x->edges[i] = NULL;
  12.     return x;
  13. }
  14. node* trie = get();
  15. string in[25010];
  16. void add(node* c, string s, int ci, int i) {
  17.     if (ci == s.size()) { c->word = i; return; }
  18.     int k = s[ci] - 'a';
  19.     if (c->edges[k] == NULL) c->edges[k] = get();
  20.     add(c->edges[k], s, ci + 1, i);
  21. }
  22. void print(node* c) {
  23.     if (c == NULL) return;
  24.     if (c->word != -1) cout << in[c->word] << '\n';
  25.     for (int i = 0; i < 26; i++) print(c->edges[i]);
  26. }
  27. void get_pref(node* c, string s, int ci) {
  28.     if (ci == s.size()) { print(c); return; }
  29.     int k = s[ci] - 'a';
  30.     if (c->edges[k] == NULL) { cout << "No match.\n"; return; }
  31.     get_pref(c->edges[k], s, ci + 1);
  32. }
  33. int main() {
  34.     int n; cin >> n;
  35.     for (int i = 0; i < n; i++) {
  36.         cin >> in[i];
  37.         add(trie, in[i], 0, i);
  38.     }
  39.     int m; cin >> m; string qs;
  40.     for (int tc = 1; tc <= m; tc++) {
  41.         cin >> qs;
  42.         cout << "Case #" << tc << ": \n";
  43.         get_pref(trie, qs, 0);
  44.     }
  45.     return 0;
  46. }
  47.  
Success #stdin #stdout 0s 3516KB
comments (?)
stdin
copy 
5
set
lol
setter
setting
settings
2
set
happy
stdout
copy 
Case #1: 
set
setter
setting
settings
Case #2: 
No match.
https://ideone.com/FxUaVp
language:
C++ (gcc 8.3)
created:
8 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!