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; } };