2229.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2229 on 2006-05-15 at 22:02:56 */ 
#include <cstdio>
#include <cctype>
#include <cstring>
#include <set>
#include <algorithm>
using namespace std;

const int L = 160;

struct cmp {
	bool operator ()(const char* s1, const char* s2) const {
		return strcmp(s1, s2) < 0;
	}
};

int main()
{
	int n, spell[L], i, j;
	set<char*, cmp> ig;
	char rule[L], igw[L][L], word[L];

	while(scanf("%d", &n) != EOF && n != 0) {
		ig.clear();
		for(i = 0; i < n; i++) {
			scanf("%s", igw[i]);
			ig.insert(igw[i]);
		}
		while(true) {
			bool end = false; memset(spell, 0, sizeof(spell));
			scanf("%s", rule); int len = strlen(rule), t;
			for(t = 0; true; t++) {
				if(getchar() == '\n') break;
				scanf("%s", word);
				if(isupper(word[0])) { end = true; break; }
				else if(ig.count(word)) { t--; continue; }
				int nxt[L] = { 0 };
				for(i = 0; word[i] != 0; i++)
					for(j = len-1; j >= 0; j--)
						if(rule[j]-'A' == word[i]-'a') 
							if(j == 0 && t == 0) nxt[j]++;
							else if(j != 0) nxt[j] += nxt[j-1]+spell[j-1];
				memcpy(spell, nxt, sizeof(nxt));
			}
			if(end) break;
			printf("%s ", rule);
			if(spell[len-1] == 0) printf("is not a valid abbreviation\n");
			else printf("can be formed in %d ways\n", spell[len-1]);
		}
	}
	
	return 0;
}