ABC287 D問題 Match or Not

atcoder.jp

2つの文字列が"マッチ"するか調べる

• 文字列 S の先頭 文字と 文字列 T の先頭 文字 が"マッチ"している。
• 文字列 S の末尾 文字と 文字列 T の末尾 文字 が"マッチ"している。

この2つの条件を満たしていれば "Yes" 、どちらか一方でも満たしていなければ "No" を返せばよいです。

を 1から まで変えた答えが求められていますが、
例えば、文字列 S の先頭から3文字目と 文字列 T の先頭から 3文字目が"マッチ"しないとき、 では "No" になります。また、文字列 S の末尾から3文字目と 文字列 T の末尾から 3文字目が"マッチ"しないとき、 つまり では "No" になります。

このことから、文字列 S と文字列 T を先頭から比べて何文字目が"マッチ"しないか、末尾から比べて何文字目が"マッチ"しないかを調べればよいことがわかります。

2つの文字の"マッチ"

2つの文字が"マッチ"するのは、

• どちらかが '?' である。
• 同じ英小文字である。

のどちらかの条件を満たしている場合です。

逆に、"マッチ"しない場合は、

• どちらかも '?' でない。
• 異なる英小文字である。

の両方を満たしている場合です。

コード例 (Julia)

function solve()

  # 入力
  S = readline()
  T = readline()

  # 文字列の長さ
  L = length(T)
  M = length(S)

  # S,T が"マッチ"しないのは先頭から何文字目か
  # (すべて一致している場合は L+1 となるように初期値設定)
  left = L+1
  for i = 1:L
    if S[i] != '?' && T[i] != '?' && S[i] != T[i]
      left = i
      break
    end
  end

  # S,T が"マッチ"しないのは末尾から何文字目か
  # (すべて一致している場合は L+1 となるように初期値設定)
  right = L+1
  for i = 1:L
    if S[M+1-i] != '?' && T[L+1-i] != '?' && S[M+1-i] != T[L+1-i]
      right = i
      break
    end
  end

  # 答え出力
  for x = 0:L
    if x >= left || x <= L - right
      println("No")
    else
      println("Yes")
    end
  end

end  # function solve


# main
solve()