SRM 593 Div2 Medium WolfDelaymaster

問題

SRM 593 - TopCoder Wiki

自然数nについて,ある文字列が次のいずれかの条件を満たす時valid wordsとする.

  • "w" * n + "o" * n + "l" * n + "f" * n
  • valid words + valid words

文字列が与えられた時,その文字列がvalid wordsかどうか判定する問題

解答

ある文字列のprefixがvalid wordsの時,そのvalid wordsはユニークに決まるので, prefixから順に成り立つvalid wordsかどうか判定し, 成り立つならその後の文字列について同様に計算, 成り立たないならばinvalidを返す.

using namespace std;

class WolfDelaymaster
{
public:
  string check(string str)
    {
      string wolf = "wolf";
      int n = str.size();
      int m = 13;
      vector<string> valid_words(m, "");
      int i, j, k;
      for(i = 1; i < m; i++){
        valid_words[i] = "";
        for (j = 0; j < wolf.size(); j++){
          for (k = 0; k < i; k++){
            valid_words[i] += wolf[j];
          }
        }
      }
      bool found = false;
      int match_pos = 0;
      do {
        found = false;
        for (int i = 1; i < m; i++) {
          if ((n - match_pos) < valid_words[i].size()) break;
          // cout << "match_pos=" << match_pos << " valid_words[i]=" << valid_words[i] << endl;
          if (str.substr(match_pos, valid_words[i].size()) == valid_words[i]) {
            found = true;
            match_pos += valid_words[i].size();
            // cout << "found! " << valid_words[i] << endl;
            break;
          }
        }
      }while(found);
      if (match_pos == n) return "VALID";
      return "INVALID";
    }
};