algospot - wildcard

//algospot - wildcard
 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int N;
string wc;
string s;
string* sarr;
vector<vector<int>> cache;
vector<string> ans;
 
void init()
{
    ans = vector<string>();
    cin >> wc;
    cin >> N;
    sarr = new string[N];
    for(int i = 0; i<N; ++i)
        cin >> sarr[i];
}
 
int dp(int widx, int sidx)
{
    if(widx == wc.size() - 1 && sidx == s.size() - 1)
        if(wc[widx] == s[sidx] || wc[widx] == '?' || wc[widx] == '*')
            return 1;
        else
            return 0;
    else if(widx == wc.size() - 1)
        if(wc[widx] == '*')
            return 1;
        else return 0;
    else if(sidx == s.size() - 1)
        if(wc[widx] == '*')
            return dp(widx+1, sidx);
        else if(wc[widx] == s[sidx])
        {
            for(int i = widx+1; i<wc.size(); ++i)
                if(wc[i] != '*')
                    return 0;
                return 1;
        }
        else
            return 0;
 
    int& ret = cache[widx][sidx];
    if(ret != -1)
        return ret;
    ret = 0;
    if(wc[widx] == '?' || wc[widx] == s[sidx])
        ret = dp(widx+1, sidx+1);
    else if(wc[widx] == '*')
    {
        ret += dp(widx, sidx+1);
        ret += dp(widx+1, sidx+1);
        ret += dp(widx+1, sidx);
    }
 
    return ret;   
}
 
void cmp(int idx)
{
    s = sarr[idx];
    cache = vector<vector<int>>(wc.size(), vector<int>(s.size(), -1));
 
    int flag = dp(0,0);
    
    if(flag)
        ans.push_back(s);  
}
 
int main()
{
    int C; cin >> C;
    for(int tn = 0; tn<C; ++tn)
    {
        init();
        for(int i = 0; i<N; ++i)
            cmp(i);
        sort(ans.begin(), ans.end());
        cout << "\n";
        for(int i = 0; i<ans.size(); ++i)
            cout << ans[i] << "\n";
        cout << "\n";
    }
}