2012年11月27日

UVa 10027 - Language Cardinality


#include <cstdio>
#include <set>
#include <string>
using namespace std;

int main() {
  int n;
  scanf("%d", &n);
  getchar();
  getchar();
  while (n--) {
    int now, l;
    char init[50];
    set<string> dic;
    gets(init);
    for (l = 0; init[l]; l++);
    init[l - 1] = '\0';
    dic.insert(string(init + 1));
    int num = 0, len[200], inf = 0;
    char s[100], ori[20][100], rep[20][100];
    while (gets(s) && s[0]) {
      int l1 = 0, l2 = 0;
      for (l = 1; s[l]; l++)
        if (s[l] == '\"') break;
        else ori[num][l1++] = s[l];
      ori[num][l1] = '\0';
      len[num] = l1;
      for (l += 4; s[l]; l++)
        if (s[l] == '\"') break;
        else rep[num][l2++] = s[l];
      rep[num][l2] = '\0';
      if (!l1 && l2) {
        inf = 1;
      } else if (l1 && l2 && l1 != l2) {
        int loc = string(rep[num]).find(ori[num]);
        if (loc >= 0 && loc < l2) inf = 1;
      }
      num++;
    }
    for (now = 0; now < num && !inf; now++) {
      int rec = dic.size();
      for (set<string>::iterator it = dic.begin(); it != dic.end() && !inf; it++) {
        string temp = *it;
        int start, add = 0;
        while (!inf) {
          start = temp.find(ori[now], add++);
          if (start < 0 || start >= temp.length()) break;
          string next(temp);
          next.erase(start, len[now]);
          next.insert(start, rep[now]);
          dic.insert(next);
          if (dic.size() > 1000) inf = 1;
        }
      }
      if (rec != dic.size()) now = -1;
    }
    if (!inf) printf("%d\n", dic.size());
    else puts("Too many.");
    if (n) puts("");
  }
  return 0;
}

2 則留言:

  1. try this case:

    1

    "A"
    "S"->"aS"

    output should be 1.

    回覆刪除
    回覆
    1. Thanks!
      已經一段時間沒碰UVa,最近較無心力,有時間再修修。

      刪除