1093.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1093 on 2006-08-16 at 19:30:16 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int L = 16;
const int S = 1 << L;
 
int csn;
 
class System {
private:
	char rule[2][L], begin[L], end[L];
	int rl[2], vst[S];
	bool dfs(char*, char*, int, int, int);
public:
	System() { memset(vst, -1, sizeof(vst)); }
	bool getContent();
	bool find(char*);
};
bool System::getContent() {
	for(int i = 0; i < 2; i++)
		if(gets(rule[i]) == NULL) return false;
		else rl[i] = strlen(rule[i]);
	gets(begin); gets(end);
	return true;
}
bool System::dfs(char* dis, char* str, int len, int ind, int dep) {
	str[dep] = 0;
	if(ind == len) return find(str);
	for(int i = 0; i < 2; i++) {
		int ml = min(len-ind, rl[i]);
		if(strncmp(dis+ind, rule[i], ml)) continue;
		str[dep] = i+'a';
		if(dfs(dis, str, len, ind+ml, dep+1)) return true;
	}
	return false;
}
bool System::find(char* dis = NULL) {
	if(dis == NULL) dis = end;
	if(strstr(begin,  dis) != NULL) return true;
	int len = strlen(dis), cd = 0; char str[L];
	for(int i = 0; i < len; i++) cd |= (dis[i]-'a') << i;
	if(vst[(1<<len)|cd] == csn) return false;
	vst[(1<<len)|cd] = csn;
	for(int j = 0; j < 2; j++)
		for(int i = 1; i <= rl[j]; i++) {
			str[0] = j+'a';
			int ml = min(len, rl[j]);
			if(i >= ml && !strncmp(dis, rule[j]+rl[j]-i, ml) && dfs(dis, str, len, ml, 1)) return true;
			if(i < ml && !strncmp(dis, rule[j]+rl[j]-i, i) && dfs(dis, str, len, i, 1)) return true;
		}
	return false;
}
 
System sys;
 
int main()
{
	for(csn = 0; sys.getContent(); csn++)
		printf("%s\n", sys.find() ? "YES" : "NO");
	return 0;
}