Uvalive 6259 Word equations dfs+dp

题意：给定一些宏以及宏的定义，问指定宏展开后是否是某个字符串的匹配串。
比如
START = FIRST + SECND
• FIRST = D + E
• SECND = F + E
• D = good
• E = times
• F = bad
START的展开为$goodtimesbadtimes$，给定一个询问。$debate$，这个串在$goodtimesbadtimes$中顺序出现。。。。

给定的宏只有两种方式 一种是 宏 = 宏 + 宏 另一种是 宏 = 单词
这样我们可以建出一个单向无环图（题目保证无环），那么对于每个节点，可以求这个节点对于给的串第i个字符开始最多能匹配的个数。依次往上推即可~~
代码：

#include <iostream>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int MAXN = 10000;
char strs[MAXN][20];
map <string,int> m;
map <string,int> ::iterator it;
char tmp[3000];
char t1[10],t2[10],t3[10];
struct Edge {
	int to,next;
	Edge(){}
	Edge(int _to,int _next):to(_to),next(_next){}
}e[20000];
int head[MAXN],tot,ctot;
void init(){
	//for(int i=0;i<=2000;i++)head[i]=-1;
	memset(head,-1,sizeof(head));
	ctot=tot=0;
}
void AddEdge(int u,int v){
	e[tot]=Edge(v,head[u]);
	head[u]=tot++;
	//while(ctot>2000)puts("fuck");
}
int Tj,len;
int has[MAXN],chas[MAXN];
int dp[MAXN][2010];
void dfs(int u){
	//if(Tj==len)return;
	has[u]=1;
	for(int i=head[u];~i;i=e[i].next){
		int v=e[i].to;
		if(has[v])continue;
		dfs(v);
	}
	int ct=0;
	if(chas[u]){
		int len1=strlen(strs[u]);
		for(int j=0;j<len;j++){
			int cnt=0;
			for(int i=0;i<len1;i++){
				if(j+cnt<len&&tmp[j+cnt]==strs[u][i])++cnt;
				//if(strs[u][i]==tmp[Tj])++Tj;
			}
			dp[u][j]=cnt;
		}
		dp[u][len]=0;
	}
	else 
		for(int i=head[u];~i;i=e[i].next){
			int v=e[i].to;
			++ct;
			if(ct==1){
				for(int j=0;j<=len;j++)dp[u][j]=dp[v][j];
			}
			else {
				for(int j=0;j<len;j++)dp[u][j]+=dp[v][j+dp[u][j]];
			}
		}
}
int main(){
	int T,n;
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		init();
		m.clear();
		getchar();
		memset(chas,0,sizeof(chas));
		for(int i=0;i<n;i++){
			fgets(tmp,sizeof(tmp),stdin);
			int flag=0;
			for(int j=0;tmp[j];j++)if(tmp[j]=='+'){flag=1;break;}
			int n1,n2,n3;
			if(flag){
                sscanf(tmp," %s = %s + %s",t1,t2,t3);
				it=m.find(t1);
				if(it==m.end()){
					strcpy(strs[ctot],t1);
					m.insert(pair<string,int>(t1,ctot++));
					n1=ctot-1;
				}
				else n1=m[t1];
				it=m.find(t2);
				if(it==m.end()){
					strcpy(strs[ctot],t2);
					m.insert(pair<string,int>(t2,ctot++));
					n2=ctot-1;
				}
				else n2=m[t2];
				it=m.find(t3);
				if(it==m.end()){
					strcpy(strs[ctot],t3);
					m.insert(pair<string,int>(t3,ctot++));
					n3=ctot-1;
				}
				else n3=m[t3];
				AddEdge(n1,n3);
				AddEdge(n1,n2);
			}
			else {
                sscanf(tmp," %s = %s",t1,t2);
				it=m.find(t1);
				if(it==m.end()){
					strcpy(strs[ctot],t1);
					m.insert(pair<string,int>(t1,ctot++));
					n1=ctot-1;
				}
				else n1=m[t1];
				it=m.find(t2);
				if(it==m.end()){
					strcpy(strs[ctot],t2);
					m.insert(pair<string,int>(t2,ctot++));
					n2=ctot-1;
				}
				else n2=m[t2];
				AddEdge(n1,n2);
				chas[n2]=1;
			}
		}
		scanf("%s",tmp);
		int nn=m[tmp];
		it=m.find(tmp);
		scanf("%s",tmp);
		if(it==m.end()){
			puts("NO");
			continue;
		}
		len=strlen(tmp);
		memset(has,0,sizeof(has));
		dfs(nn);
		if(dp[nn][0]==len)puts("YES");
		else puts("NO");
	}
	return 0;
}