abc268d ac

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#define dbg(...) logger(#__VA_ARGS__, __VA_ARGS__)
template <typename... Args> void logger(string vars, Args &&... values)
{
    cerr << vars << " = ";
    string delim = "";
    (..., (cerr << delim << values, delim = ", "));
    cerr << endl;
}

template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;
using ll = long long;
using pii = pair<int, int>;

int n, m;
namespace AC
{
const int MAXL = int(1e5 + 3);
const int WIDTH = 27;
int trie[MAXL << 4][WIDTH], hit[MAXL << 4], tcnt;
int fail[MAXL << 4];
void init()
{
    memset(fail, 0, sizeof(fail));
    memset(trie, 0, sizeof(trie));
    memset(hit, 0, sizeof(hit));
    tcnt = 0;
}
void insert(const char *s)
{
    int u = 0;
    for (int i = 0; s[i]; ++i) {
        const int offset = (s[i] == '_' ? 26 : s[i] - 'a');
        if (!trie[u][offset])
            trie[u][offset] = ++tcnt;
        u = trie[u][offset];
    }
    hit[u] = 1;
}
void build()
{
    queue<int> q;
    for (int i = 0; i < WIDTH; ++i)
        if (trie[0][i])
            q.push(trie[0][i]);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = 0; i < WIDTH; ++i) {
            if (trie[u][i]) {
                fail[trie[u][i]] = trie[fail[u]][i];
                q.push(trie[u][i]);
            } else {
                trie[u][i] = trie[fail[u]][i];
            }
        }
    }
}
int query(const char *s)
{
    int u = 0;
    for (int i = 0; s[i]; ++i) {
        const int offset = (s[i] == '_' ? 26 : s[i] - 'a');
        u = trie[u][offset];
        if (u == 0)
            return 1;
    }
    if (hit[u]) {
        return 0;
    }
    return 1;
}
}; // namespace AC

char s[8][1 << 5];

char ans[1 << 5];
int dfs(char *permu[], int n, int arr_idx, int pos, int blank)
{
    if (arr_idx == n) {
        ans[pos] = 0;
        if (strlen(ans) < 3)
            return 0;
        int ret = AC::query(ans);
        // fprintf(stderr, "ans:%s ret:%d\n", ans, ret);
        return ret;
    }
    if (pos + strlen(permu[arr_idx]) > 16)
        return 0;
    int slen = strlen(permu[arr_idx]);
    memcpy(ans + pos, permu[arr_idx], slen);
    pos += slen;
    if (arr_idx == n - 1) {
        return dfs(permu, n, arr_idx + 1, pos, blank);
    } else
        for (int i = 0; i < blank - (n - pos - 1); ++i) {
            ans[pos + i] = '_';
            if (dfs(permu, n, arr_idx + 1, pos + i + 1, blank - i - 1))
                return 1;
        }
    return 0;
}

int main(int argc, char **argv)
{
    char buf[1 << 5];
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i)
        scanf("%s", s[i]);

    AC::init();
    for (int i = 0; i < m; ++i)
        scanf("%s", buf), AC::insert(buf);
    // AC::build();

    if (n == 1 && strlen(s[0]) < 3) {
        printf("-1\n");
        return 0;
    }
    char *permu[8];
    int len = 0;
    for (int i = 0; i < n; ++i)
        permu[i] = s[i], len += strlen(s[i]);

    do {
        int ret = dfs(permu, n, 0, 0, 16 - len);
        if (ret) {
            printf("%s\n", ans);
            return 0;
        }
    } while (next_permutation(permu, permu + n));

    printf("-1\n");
    return 0;
};