2013年8月20日

UVa 148 - Anagram checker

#include <cstdio>
#include <cstring>
#include <sstream>
#include <vector>
#include <map>
#include <algorithm>
#define PB push_back
using namespace std;

char s[99], word[2222][22];
int N, len[2222];
vector<int> originSet;

void find(int index, int remain, int * need, vector<int> & used) {
  if (!remain) {
    if (used != originSet) {
      printf("%s = ", s);
      for (int i = 0; i < used.size(); i++) {
        printf("%s%s", word[used[i]], i == used.size() - 1 ? "\n" : " ");
      }
    }
    return;
  }
  if (index >= N) {
    return;
  }
  int temp[26];
  memcpy(temp, need, sizeof(temp));
  bool add = true;
  for (int i = 0; word[index][i] && add; i++) {
    char c = word[index][i] - 'A';
    need[c]--;
    add = (need[c] >= 0);
  }
  if (add) {
    used.PB(index);
    find(index + 1, remain - len[index], need, used);
    used.pop_back();
  }
  memcpy(need, temp, sizeof(temp));
  find(index + 1, remain, need, used);
  memcpy(need, temp, sizeof(temp));
}

int main() {
  map<string, int> indexOf;
  while (gets(word[N]) && word[N][0] != '#') {
    len[N] = strlen(word[N]);
    indexOf[word[N]] = N;
    N++;
  }
  while (gets(s) && s[0] != '#') {
    int remain = 0, need[26] = {};
    for (int i = 0; s[i]; i++) {
      if (s[i] == ' ') {
        continue;
      }
      need[s[i] - 'A']++;
      remain++;
    }
    originSet.clear();
    istringstream ss(s);
    string tmp;
    while (ss >> tmp) {
      if (indexOf.count(tmp)) {
        originSet.PB(indexOf[tmp]);
      }
    }
    sort(originSet.begin(), originSet.end());
    vector<int> used;
    find(0, remain, need, used);
  }
  return 0;
}

沒有留言:

張貼留言