계기

• 정우가 학교에서 대회를 여는데 구현 위주의 문제이고, 한번 풀어봐달라고 해서 푼 코드

  #include <iostream>
  #include <vector>
  #include <string>
  #include <set>
  #include <algorithm>
      
  using namespace std;
  set<string> visited;
  bool chk(string data, vector<int> count)
  {
    for (auto& c : data) count[c-'a'] --;
      
    for(int i=0;i<26;i++) 
      if (count[i] != 0) return false;
      
    return true;
  }
      
  vector<string> gen(string data) {
    vector<string> retval;
    string f, b, f_r, b_r;
    vector<string> r;
    if (data.size() == 1) 
      retval.push_back(data);
      
    else if (data.size() % 2 == 0) {
      f = data.substr(0, data.size() / 2); b = data.substr(data.size() / 2);
      
      r = gen(b); f_r = f; reverse(f_r.begin(), f_r.end());
      for (auto& d : r) retval.push_back(f_r+d);
      
      r = gen(f); b_r = b; reverse(b_r.begin(), b_r.end());
      for (auto& d : r) retval.push_back(d+b_r);
      
    } else {
      f = data.substr(0, data.size() / 2); b = data.substr(data.size() / 2);
      
      r = gen(b); f_r = f; reverse(f_r.begin(), f_r.end());
      for (auto& d : r) retval.push_back(f_r+d);
      
      r = gen(f); string b_r = b; reverse(b_r.begin(), b_r.end());
      for (auto& d : r) retval.push_back(d+b_r);
      
      f = data.substr(0, data.size() / 2 + 1); b = data.substr(data.size() / 2 + 1);
      
      r = gen(b); f_r = f; reverse(f_r.begin(), f_r.end());
      for (auto& d : r) retval.push_back(f_r+d);
      
      r = gen(f); b_r = b; reverse(b_r.begin(), b_r.end());
      for (auto& d : r) retval.push_back(d+b_r);
    }
    return retval;
  }
      
  void solve(string data) {
    vector<string> s = gen(data);
    for(auto& d : s) {
      visited.insert(d);
    }
  }
      
      
  int main (){
    int n, cnt, length;
    string input;
    char a;
      
    scanf("%d", &n);
    vector<int> count(26, 0);
      
    length = 0;
    for (int i=0;i<n;i++) {
      scanf(" %c %d", &a, &cnt);
      count[a-'a'] += cnt;
      length += cnt;
    }
      
    cin >> input;
      
    for (int i=0;i<=input.length() - length;i++){
      string tmp = input.substr(i, length);
      if(chk(tmp, count))
        solve(tmp);
    }
      
    printf("%d", (int)visited.size());
    return 0;
  }