解法1

\(T\) の ? に具体的な a から z の文字を当てはめて得られる \(S\) の候補をすべて探索し，\(S\) が \(U\) を連続部分文字列として含むか判定すればよいです．

\(S\) としてあり得る候補は \(26^4=456976\) 個であり，4重の for ループにより高速に列挙することができます．

\(S\) が \(U\) を連続部分文字列として含むかどうかの判定も2重の for ループにより行えます．\(S\) が \(U\) を連続部分文字列として含む位置の候補は \(|S|-|U|+1\) 通りあり，それらをすべて全探索して，対応する位置にある文字が一致するかどうか判定すればよいです．

また，言語によっては，連続部分文字列があるか判定する標準機能が実装されている場合があります．C++ の場合は find 関数を，Python の場合は in 演算子を用いることができます．

実装例 (C++)

実装例 (Python)

解法2

\(S\) を具体的に決めなくても，2重の for 文のみで問題を解くことができます．

\(S\) が \(U\) を連続部分文字列として含む位置の候補 \(|S|-|U|+1\) 通りを全探索し，\(S\) の \(i\) 文字目から \(i+|U|-1\) 文字目が \(U\) に一致しうるか判定します．一致する条件は以下の通りです．

• \(j=1,2,\dots,|U|\) について，\(T_{i+j} =\) ? または \(T_{i+j} = U_j\)

この条件を満たしているとき， \(T_{i+j}=\) ? を \(U_j\) で置き換えることで \(S_{i+j}=U_j\) とできるので，部分文字列を一致させられます．よってこの条件は十分条件です．

また，ある \(j\) について \(T_{i+j} \neq\) ? かつ \(T_{i+j} \neq U_j\) ならば，必ず \(S_{i+j} \neq U_j\) となり，部分文字列が一致することはありません．よってこの条件は必要条件です．

実装例 (C++)

実装例 (Python)