SRM154 Div1 350pt CheatCode

http://www.topcoder.com/stat?c=problem_statement&pm=1779&rd=4575
簡易NFSA(非決定性有限オートマトン)を作る問題。
実際自分は適当にfor文でごり押ししたら通っちゃったけど、ほかの人のソース見てきれいなのがあったから、今後のために書いておく。


まず

fsa[現在の状態][入力] = 次の状態(遷移先)

という感じでテーブルを作っておく。


次にNFSAといえばバックトラックだから再帰で書くのかなぁと思いきや、幅優先探索っぽいことをしている。
幅優先探索は大体以下のように書く。

vector<State> cur, next;
cur.push_back(start_state);
for (int step = 0; !cur.empty(); step++)
  for (int k = 0; k < cur.size(); k++) {
    State& s = cur[k];
    //Proc
    //  next.push_back(next_state);
    //Proc
  }
  cur.swap(next);
  next.clear();
}

初めてこれを見たときすごい感動したのだけれど、自分がこれを知ったときには、周りではコモンセンスになっているみたいだった。これだとqueueを使ってwhileでまわすのと違って状態の中にステップ数を持たなくてすむ。


だいぶ幅優先の話になってしまったが、NFSAの話に戻ると、この問題は一文字ずつ入力されていくので先ほどのstepでまわしたループでstring中の文字を一文字ずつ読み込む処理と置き換えることができる。
実際にコードにすると

vector<int> cur(1,0), next(1,0);
for (int p = 0; p < input.size(); p++) {
  for (int k = 0; k < cur.size(); k++) {
    //終了処理(受理の処理)
    next.push_back(fsa[cur[k]][input[p]]);
  }
  cur.swap(next);
  make_unique(cur); //同じものが無いようにする関数(sortしてuniqueする)
  next.resize(1,0);
}

といった感じになる。Stateはint,start_stateは0,stepはpに置き換わったと思ってほしい。next.resize(1,0);というのはこの問題では常に初期状態に戻ることが可能なのでclear()の代わりに使っている。


まぁ何いってるのかわからないかもしれないので、もうコード全部のっけておく。長くなって申し訳ない。

#include <vector>
#include <string>
#include <algorithm>
using namespace std;
template<class T> void make_unique(T& v) {
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(),v.end()), v.end());
}
class CheatCode {
public:
  vector<int> matches(string keyPresses, vector <string> codes) {
    vector<int> ret;
    for (int i = 0; i < codes.size(); i++)
      if (check(keyPresses, codes[i])) ret.push_back(i);
    return ret;
  }
  bool check(const string& input, const string& code) {
    vector<vector<int> > fsa(code.size(),vector<int>(256));
    fsa[0][code[0]] = 1;
    for (int i = 1; i < code.size(); i++) {
      fsa[i][code[i-1]] = i;
      fsa[i][code[i]] = i+1;
    }
    vector<int> cur(1,0), next(1,0);
    for (int p = 0; p < input.size(); p++) {
      for (int k = 0; k < cur.size(); k++) {
        if (fsa[cur[k]][input[p]] == code.size())
          return true;
        if (fsa[cur[k]][input[p]])
          next.push_back(fsa[cur[k]][input[p]]);
      }
      cur.swap(next);
      make_unique(cur);
      next.resize(1,0);
    }
    return false;
  }
};