2245.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 2245 on 2006-05-22 at 20:48:26 */ 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int L = 24;
const int WN = 128;

class Word {
public:
	char name[L];
	int len;
	int make();
	bool overlop(const Word&) const;
};
int Word::make() {
	if(scanf("%s", name) != 1) return -1;
	len = strlen(name);
	return (name[0] != '*');
}
bool Word::overlop(const Word& w) const {
	if(!strcmp(name, w.name)) return false;
	int i, l = min(w.len, len);
	for(i = 1; i <= l; i++)
		if(!strncmp(name+len-i, w.name, i)) break;
	return (i != w.len && i <= l);
}

int main()
{
	int n, i, j, st[WN];
	bool nxt[WN][WN];
	Word w[WN];
	
	while(true) {
		for(n = 0; true; n++) {
			int r = w[n].make();
			if(r == -1) return 0;
			else if(r == 0) break;
		}
		memset(nxt, false, sizeof(nxt));
		for(i = 0; i < n; i++)
			for(j = 0; j < n; j++)
				if(w[i].overlop(w[j])) nxt[i][j] = true;
		memset(st, 0, sizeof(st));
		while(true) {
			bool ud = false;
			for(i = 0; i < n; i++) {
				if(st[i] != 0) continue;
				bool uc = false;
				for(j = 0; j < n; j++)
					if(!nxt[i][j]) continue;
					else if(st[j] == 1) { st[i] = -1; break; }
					else if(st[j] == 0) uc = true;
				if(st[i] == 0 && !uc) st[i] = 1;
				if(st[i] != 0) ud = true;
			}
			if(!ud) break;
		}
		int pn = 0;
		for(i = 0; i < n; i++)
			if(st[i] == 1) { printf("%s%s", pn == 0 ? "" : " ", w[i].name); pn++; }
		if(pn == 0) printf("No winning word");
		putchar('\n');
	}
}