\(S_i\) とどの位置でも一致しない文字列は，\(S_i\) の 0, 1 を反転させた文字列 (\(S'_i\) とおく) のみです．

よって，\(S'_1, \dots, S'_N\) のいずれでもない長さ \(M\) の文字列であることが答えの条件と等価です．

\(m = \lceil \log_{2} (N+1) \rceil\) とします．

\(M < m\) の場合

\(2^M\) 通りの \(T\) のうち，\(S'_1, \dots, S'_N\) のいずれとも異なるものを求めればよいです．これは，長さ \(2^M\) の 0 埋め配列を用意し，添字 \(S'_1, \dots, S'_N\) の要素を 1 にしてから，値が 0 の添字を探すことで求まります．

\(M \geq m\) の場合

• \(S'_1, \dots, S'_N\) それぞれの冒頭 \(m\) 文字の接頭辞は高々 \(N\) 種類
• \(T\) の冒頭 \(m\) 文字の接頭辞がとりえる種類数は \(2^m = 2^{\lceil \log_{2} (N+1) \rceil}\)

\(2^m = 2^{\lceil \log_{2} (N+1) \rceil} \geq N+1 > N\) より，\(S'_1, \dots, S'_N\) それぞれの冒頭 \(m\) 文字のいずれでもない長さ \(m\) の文字列が存在します．これを接頭辞とする \(T\) を任意にとれば，それが答えとなります．

長さ \(m\) の接頭辞の求め方は \(M < m\) の場合と同様です．

計算量

\(2^{\min(M, m)} = O(N)\) なので，各場合の計算量はいずれも \(O(NM)\) です．

原案：sheyasutaka