#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; }
Hello, I am a CS student from Taiwan.
I am learing English and Programming.
I'll save source code of some problems or small programs without comments in this blog.
I would recommend you not to read solution from others before you solved the problem.
(這邊專門存放沒有任何註解的小程式/OJ題目程式碼)
2012年11月27日
UVa 10027 - Language Cardinality
訂閱:
張貼留言 (Atom)
try this case:
回覆刪除1
"A"
"S"->"aS"
output should be 1.
Thanks!
刪除已經一段時間沒碰UVa,最近較無心力,有時間再修修。