UVA_310
一般LRJ选出来的但用户solve率这么少的题目大概都是有trick的，几个月前写过一次，结果交上去只有三种情况WA、TLE、RE。今天又写了一下，结果出乎意料地AC了，所以也说不清当初卡在哪里了。
说一说这次的思路吧，首先a和b的转换字符串u、v都是非空的，w也是非空的，但z可能为空，每次替换都需要把字符串中所有a替换成u，所有的b替换成v，第一次写的时候对这个替换的规则审题审了好久，后来偶然有个机会研究了一下L-System并用Java画了几个L-System的图形，这才对L-System的字符串的演变规则有了更深一点的了解。
明确了规则之后，需要再理解一下下面这个命题，如果一个字符串s演变出来的字符串包含z，那么s的所有长度为z的子串演变出来的字符串中也必定有某一个字符串会包含z。如果s本身长度没有达到z也没关系，那就相当于它只有一个子串就是它本身。
这样，我们就只要每次截取长度为z或小于z的子串保留下来，然后不断以此为基础进行拓展即可，可以用哈希表对字符串判重。这样当遇到z就退出即可，如果所有的串都拓展并找完了还没有z的话，自然就是无解了。
对于哈希函数我们可以不必选取字符串的哈希函数，因为这个题目本身可以用类似2进制的方式构造出完美哈希，而且空间只需要2^16。
#include<stdio.h>
#include<string.h>
#define MAXD 600000
#define HASH 70000
char a[110], b[110], w[20], z[20], st[MAXD][20], t[210];
int next[MAXD], hash[HASH], Z;
void solve()
{
int i, j, k, front, rear, v;
front = rear = 0;
memset(hash, 0, sizeof(hash));
Z = 0;
for(i = 0; z[i]; i ++)
Z = Z * 2 + z[i] - 'a' + 1;
for(i = 0; w[i]; i ++)
{
v = 0;
for(j = i, k = 0; w[j] && z[k]; j ++, k ++)
{
v = v * 2 + w[j] - 'a' + 1;
st[rear][k] = w[j];
}
st[rear][k] = '\0';
if(!hash[v])
{
hash[v] = 1;
++ rear;
}
}
while(front < rear)
{
if(hash[Z])
break;
for(i = j = 0; st[front][i]; i ++)
{
if(st[front][i] == 'a')
{
for(k = 0; a[k]; k ++)
t[j ++] = a[k];
}
else
{
for(k = 0; b[k]; k ++)
t[j ++] = b[k];
}
}
t[j] = '\0';
for(i = 0; t[i]; i ++)
{
v = 0;
for(j = i, k = 0; t[j] && z[k]; j ++, k ++)
{
st[rear][k] = t[j];
v = v * 2 + t[j] - 'a' + 1;
}
st[rear][k] = '\0';
if(!hash[v])
{
hash[v] = 1;
++ rear;
}
}
front ++;
}
if(front != rear)
printf("YES\n");
else
printf("NO\n");
}
int main()
{
while(gets(a) != NULL)
{
gets(b);
gets(w);
gets(z);
if(z[0] == '\0')
printf("YES\n");
else
solve();
}
return 0;
}