はじめに

本問では長さが \(16\) 以下の文字列の比較や構築を多く行います。本解説中ではこれらの処理が \(\mathrm{O}(1)\) であるとします。

解法の概要

本問は条件のうち \(1\) 番目と \(2\) 番目を満たすものを効率的に生成し、それが \(T_1,T_2,\ldots,T_M\) のいずれかと一致するかどうかを高速に判定すれば解けます。

\(1\) 番目と \(2\) 番目の条件を満たす文字列の生成

\(1\) 番目の条件の \(1\) 文目に「\(N\) 個の文字列 \(S_1,S_2,\ldots,S_N\) を好きな順番で並べたものを \(S_1', S_2', \ldots,S_N'\) とする」とあります。これは、例えばC++であればnext_permutationを用いて生成することが出来ます(参考 next_permutationを使う過去の問題例)。 続いて「\(S_1'\)、( \(1\) 個以上の _ )、\(S_2'\)、( \(1\) 個以上の _ )、\(\ldots\)、( \(1\) 個以上の _ )、\(S_N'\) をこの順番で連結したものを \(X\) とする」とあります。また、\(2\) 番目の条件として「\(X\) の文字数は \(3\) 以上 \(16\) 以下である」とあります。これらを満たす条件の生成する方法はいろいろと考えられますが、ここでは再帰によるものを示します。
再帰関数の引数として生成途中の文字列と\(S_1',S_2',\ldots,S_N'\) のうち何番目まで使ったかを持たせます。そして、現在の文字列の末尾に _ が必要なら追加し、そうでない場合は \(S_1',S_2',\ldots,S_N'\) のうち次のものを末尾に追加するか、可能なら( \(S_1',S_2',\ldots,S_N'\) のうちまだ使っていないものと必ず発生する _ を追加しても \(16\) 文字を超えないならば) _ を末尾に追加することにします。そして、\(S_1',S_2',\ldots,S_N'\) をすべて使ったらその時点で条件のうち \(1\) 番目と \(2\) 番目を満たすものが生成されたことになります。
ここで生成された文字列が \(T_1,\ldots,T_M\) のいずれかと一致するか判定し、いずれとも一致しなければ出力をしプログラムを終了する、とすることで条件を満たす文字列を求める(または存在しないと判定する)ことが出来、本問に正解出来ます。 実装例では cur として \(S_1',S_2',\ldots,S_N'\) のうち何番目まで使ったかを、ans として生成途中の文字列を持たせています。また、remain として余分に追加できる _ の個数を保持している他に \(S_1',S_2',\ldots,S_N'\) や \(T_1,T_2,\ldots,T_M\) も持たせていますが、これらはお好みでグローバル空間においても良いと思います。

\(M\) 個の文字列のいずれかと一致するかどうかの判定

生成された文字列が \(T_1,T_2,\ldots,T_M\) のいずれかと一致するかどうかの判定ですが、生成される文字列の候補数がそれなりに多いため(後述)、毎回 \(\mathrm{O}(M)\) かけて判定すると間に合いません。
データ(今回は文字列)の列 \(T\) にあるデータ \(x\) が含まれているかどうかを効率的に判定する方法として、列をあらかじめソートしたうえで二分探索を行うという方法があります。C++を始めとした多くの言語では

if(binary_search(T.begin(),T.end(),x)){
	//something
}

等のようにすることで \(x\) が含まれているかどうかを得て処理の分岐を行うことが出来ます。この方法による判定は \(\mathrm{O}(\log |T|)\) で、本問においては十分に高速となります。

実行時間の見積もり

上記のアルゴリズムを実行する上で実行時間がどの程度になるかを見積もります。文字列の生成は \(\mathrm{O}(1)\)、判定は \(\mathrm{O}(\log M)\) と分かっているため、あとは文字列の生成される回数が分かれば良いです。
まず、本解説の方法で生成される文字列は相異なります(というより、生成される文字列が相異なるような方法を与えています)。そして、生成された文字列が \(T_1,T_2,\ldots,T_M\) のいずれとも一致しなければそれを出力して終了し、そうでなければ実行が続くのですが、\(T_1,T_2,\ldots,T_M\) のいずれかと一致する回数は \(M\) 回以下です(鳩ノ巣原理)。そのため、計算量は \(\mathrm{O}(M\log M)\)とすることが出来ます。
ところで、人によっては文字列をすべて生成し終わってからそれぞれに対して判定を行おうと考えるかもしれません。仮にこの方針を採る場合、\(1\) 番目と \(2\) 番目の条件を満たす文字列をすべて生成するまでプログラムの実行が終わらないため、生成され得る文字列の個数を考える必要があります。
\(N\geq 2\) とします。\(N\) として考えられる値それぞれに対し、最悪のケースは長さ \(1\) の文字列が \(N\) 個ある場合です。まず、\(S_1',S_2',\ldots,S_N'\) が \(N!\) 通りあります。そして、それぞれに対して\(16-(2N-1)\) 個の _ を \(N\) 箇所の隙間に入れる方法と同じだけ文字列の生成方法があります(\(N-1\) 箇所の隙間は \(S_1',S_2',\ldots,S_N'\) の間で、残りの \(1\) つは文字数が \(16\) に満たない場合捨てる分です)。これは \(_{16-N}C_{N-1}\) 通りです。よって最悪ケースにおいて生成される文字列の個数は \(N!_{16-N}C_{N-1}\) となり、これは \(2\leq N \leq 8\) の範囲内でさほど大きくならないことが確かめられます。
また、このような組み合わせの計算を行わなくても、実際に生成するプログラムを書いてしまえれば再帰関数の呼び出し回数をカウントする等の方法で実行時間の問題が生じないことを確かめられます(個人的にはこちらがおすすめです)。

実装例

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

void dfs(int cur,vector<string> &S,vector<string> &T,int remain,string ans){
	
	if(remain<0)return;
	
	if(cur == S.size()){
		if(ans.size()>=3&&!binary_search(T.begin(),T.end(),ans)){
			cout<<ans<<endl;
			exit(0);
		}
		return;
	}
	
	if(ans.size()>0 && ans.back()!='_'){
		dfs(cur,S,T,remain,ans + "_");
	}
	else{
		dfs(cur+1,S,T,remain,ans + S[cur]);
		if(ans.size()>0)dfs(cur,S,T,remain-1,ans + "_");
	}
	
}

int main() {
    
	int N,M;
	cin>>N>>M;
	
	vector<string> S(N);
	for(int i=0;i<N;i++)cin>>S[i];
	sort(S.begin(),S.end());
	
	vector<string> T(M);
	for(int i=0;i<M;i++)cin>>T[i];
	sort(T.begin(),T.end());
	
	int remain = 16;
	for(int i=0;i<N;i++)remain -= S[i].size();
	remain -= N-1;	
	
	do{
		dfs(0,S,T,remain,"");
	}
	while(next_permutation(S.begin(),S.end()));
	
	cout<<-1<<endl;
	
	return 0;
}