SPOJ DICT

#define ll long long
#include <bits/stdc++.h>
using namespace std;

const int OO = 1e9;
const double EPS = 1e-9;

string output = "";

class trie {
    trie * c[26];
    bool flag;

    public:
    trie() {
        memset(c,0,sizeof(c));
        flag = 0;
    }

    void add(string &s, int idx = 0) {
        if(idx == s.size()) {
            flag = 1;
            return;
        }
        int curr = s[idx]-'a';
        if(c[curr] == 0) {
            c[curr] = new trie();
        }
        c[curr]->add(s,idx+1);
    }

    bool printPrefix(string &s, int idx = 0, int oi = 0) {
        bool ret = 0;
        if(idx == s.size()) {
            if(flag) {
                //cout << "here\n";
                //cout << "output is " << output << "\n";
                if(oi > 0) {
                    cout << s << output.substr(0,oi) << "\n";
                    ret = 1;
                }
            }
            for(int i = 0; i < 26; i++) {
                if(c[i]) {
                    if(oi < output.length()) {
                        output[oi] = (char) ('a'+i);
                    }
                    else {
                        output += (char) ('a'+i);
                    }
                    ret |= c[i]->printPrefix(s,idx,oi+1);
                }
            }
        }
        else {
            int curr = s[idx]-'a';
            if(c[curr] == 0) {
                return 0;
            }
            ret = c[curr]->printPrefix(s,idx+1,oi);
        }
        return ret;
    }
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,k;
    cin >> n;
    trie dict;
    for(int i = 0; i < n; i++) {
        string s;
        cin >> s;
        dict.add(s);
    }
    cin >> k;
    for(int ti = 1; ti <= k; ti++) {
        cout << "Case #" << ti << ":\n";
        string s;
        cin >> s;
        if(!dict.printPrefix(s)) {
            cout << "No match.\n";
        }
    }
    return 0;
}