第二回 アルゴリズム実技検定 D - パターンマッチ 解説

問題

問題文は本家サイトにあります：第二回 アルゴリズム実技検定 D - パターンマッチ

問題概要

英小文字から成る文字列 $S$ が与えられます。文字列 $T$ が次の条件を満たすとき、 $T$ は $S$ とマッチする、ということにします。

条件： $T$ は英小文字と '.' からなる文字列で、'.' をそれぞれ好きな英小文字に置き換えると、 $S$ のある連続部分文字列と一致するようにできる。

長さが $1$ 以上 $3$ 以下の文字列で $S$ とマッチするものの個数を答えなさい。

制約

$S$ は英小文字から成る文字列で、長さは $1$ 以上 $100$ 以下。

解説

リンク先の入力例にもありますが、ab なら、'a', 'b', 'ab' 以外に、'.', 'a.', '.b', '..' があり、7個となります。このくらいなら書き出せますが、他の入力例 'aabbaabb' を考えると大変そうですね。

'aabbaabb' の例を考えてみましょう。3文字でこれとマッチするものを考えてみます。'.' を含まないものは、前から順番に考えると、 'aab', 'abb', 'bba', 'baa' の4つだとわかります。他はダブってしまいます。また、 '.' を含むものは、これらの文字列のどれかを '.' に変えたものだけになることがわかるでしょう。例えば、 'aab' をベースにすれば、 'a..' や '.ab' などが該当します。

この例からもわかりますが、'.' を含まない文字列を考えた場合でも、結構重複があります。 '.' を含むものも重複が発生するので、重複を除いて正確に数えるのはすごく難しそうです。

こうした場合には、集合 set を使うといいです。set は、重複するデータをもつことができませんが、この性質を使って、とりあえず条件に合うものをどんどんいれていけばいいです。

$S$ から、1文字、2文字、3文字の連続部分文字列を順番に抜き出します。これらに対して、いくつかの場所を '.' に変えたものを作ります（「いくつか」は0でもよい、つまり、'.' に変えなくてもOK）。こうしてできる文字列を set に追加していき、要素数を返せば答えになります。

'.' に置き換えた文字列を作るところは、ビット演算を使うとやりやすいでしょう。例えば、'aab' という3文字の場合に、'.' で置き換えた文字列を作る方法を考えます。これは、2進数の $000_{(2)}$ から $111_{(2)}$ を用意して、 $1$ となっている場所を '.' に置き換える、というような処理でできます。

以上のことを踏まえれば、C++では、以下のようにして書くことができます。（下のコードでは、先ほどの説明とは異なり、 $1$ の場所と '.' の箇所が左右反転していますが、全列挙しているので集合としては同じ結果になります。）

#include <iostream>
#include <set>
#include <string>
using namespace std;

set<string> st;

void update(string s) {
  int N = (1 << s.size());
  for (int i = 0; i < N; i++) {
    string t = s;
    for (int j = 0; j < s.size(); j++) {
      if (i & (1 << j)) t[j] = '.';
    }
    st.insert(t);
  }
}

int main() {
  string S; cin >> S;

  for (int i = 0; i < S.size(); i++) {
    update(S.substr(i, 1));
    update(S.substr(i, 2));
    update(S.substr(i, 3));
  }

  cout << st.size();
  return 0;
}