SRM 433 Div1 Easy

MagicWords.cpp

class MagicWords
{
  void permute0(size_t i, vector<int> &used, vector<int> &path, const vector<int> &v, vector<vector<int> > &result){
    if(i == v.size()){
      result.push_back(path);
      return;
    }
    for(int j = 0; j < int(v.size()); j++){
      if(used[j] != 1){
        used[j] = 1;
        path.push_back(v[j]);
        permute0(i+1,used,path,v,result);
        path.pop_back();
        used[j] = 0;
      }
    }
  }

  void permute(const vector<int> &v, vector<vector<int> > &result){
    vector<int> path, used(v.size());
    permute0(0,used,path,v,result);
  }

public:
  int count(vector <string> S, int K)
  {
    vector<vector<int> > result;
    vector<int> v(S.size());
    for(int i = 0; i < int(S.size()); ++i){
      v[i] = i;
    }
    permute(v,result);
    //debug(result);
    int res = 0;
    for(int i = 0; i < int(result.size()); ++i){
      vector<int> &vv = result[i];
      string s;
      for(int j = 0; j < int(vv.size()); ++j){
        s += S[vv[j]];
      }
      if(int(s.size()) % K != 0) return 0;
      int siz = s.size();
      for(int j = 1; j <= siz/ K; ++j){
        if(siz % j != 0) continue;
        string res2 = s.substr(0,j);
        for(int k = 1; k < int(s.size())/j; ++k){
          if(res2 != s.substr(j*k,j)){
            goto fail;
          }
        }
        if(j == int(s.size())/K){
          res++;
          break;
        }else{
          goto fail2;
        }
      fail:;
      }
    fail2:;
    }
    return res;
  }