Untitled

#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int maxn = 205;
const int alphabet_size = 26;
map at_trie_is_end_of_word;
int trie[maxn][alphabet_size];
ll dp[28][1 << 9][maxn];
int o, n;
ll rec(int at, int visited, int at_trie) {
    if(at == o and __builtin_popcount(visited) == n) {
        return 1;
    }
    if(at >= o) {
        return 0;
    }
    if(dp[at][visited][at_trie] != -1) {
        return dp[at][visited][at_trie];
    }
    ll res = 0;
    for(char c = 'a'; c <= 'z'; c++) {
        int id = trie[at_trie][c - 'a'];
        res += rec(at + 1, (visited | at_trie_is_end_of_word[id]), id);
    }
    return dp[at][visited][at_trie] = res;
}
void generate_strings(int at, int visited, int at_trie, string tmp) {
    if(at == o and __builtin_popcount(visited) == n) {
        cout << tmp << endl;
        return;
    }
    if(at >= o) {
        return;
    }
    for(char c = 'a'; c <= 'z'; c++) {
        int id = trie[at_trie][c - 'a'];
        if(rec(at + 1, visited | at_trie_is_end_of_word[id], id) > 0) {
            generate_strings(at + 1, visited | at_trie_is_end_of_word[id], id, tmp + c);
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin >> o >> n;
    memset(dp, -1, sizeof dp);
    vector v(n);
    for(int i = 0; i < n; i++) {
        cin >> v[i];
    }
    int idx = 1;
    map m1;
    map m2;
    for(int i = 0; i < n; i++) {
        string tmp = "";
        for(int j = 0; j < (int) v[i].size(); j++) {
            tmp += v[i][j];
            m1[tmp] = idx;
            m2[idx] = tmp;
            idx++;
            
        }
    }
    m1[""] = 0;
    m2[0] = "";
    for(int i = 0; i <= 100; i++) {
        if(m2.find(i) != m2.end()) {
            for(int j = 0; j < n; j++) {
                if((int) m2[i].size() >= (int) v[j].size() and m2[i].find(v[j]) != string::npos) {
                    at_trie_is_end_of_word[i] |= (1 << j);
                }
            }
        }
        string tmp = "";
        for(char c = 'a'; c <= 'z'; c++) {
            tmp = m2[i] + c;
            while(m1.find(tmp) == m1.end()) {
                tmp.erase(tmp.begin());
            }
            trie[i][c - 'a'] = m1[tmp];
        }
        
    }
    
    ll res = rec(0, 0, 0);
    cout << res << endl;
    if(res < 30) {
        generate_strings(0, 0, 0, "");
    }
    return 0;
}