可能是某些我没考虑到的情况罢（）

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int maxn = 205;

int W, I, N, G, a[maxn];
vector<int> v[100];
char to[5] = {'0', 'W', 'I', 'N', 'G'};
string s;
bool dp[maxn][maxn][5];;

int change(char x) {
	if(x == 'W') return 1;
	else if(x == 'I') return 2;
	else if(x == 'N') return 3;
	else if(x == 'G') return 4;
}

void inputc(int d, char c) {
	for(int i = 1; i <= d; i++) {
		string x;
		cin >> x;
		int p = change(x[0]), q = change(x[1]);
		v[p*10 + q].push_back(change(c));
	}
}

int main() {
	cin >> W >> I >> N >> G;
	inputc(W, 'W');
	inputc(I, 'I');
	inputc(N, 'N');
	inputc(G, 'G');
	
	cin >> s;
	int n = s.size();
	for(int i = 0; i < n; i++)
		a[i+1] = change(s[i]);
	
	for(int i = 1; i <= n; i++)
		dp[i][i][a[i]] = true;
	for(int i = 1; i < n; i++) {
		int p = a[i]*10 + a[i+1];
		for(int j = 0; j < v[p].size(); j++)
			dp[i][i+1][v[p][j]] = true;
	}
	
	for(int d = 3; d <= n; d++)
	for(int i = 1; i+d-1 <= n; i++) {
		int j = i+d-1;
		for(int k = i; k < j; k++)
		for(int p = 1; p <= 4; p++)
		for(int q = 1; q <= 4; q++) {
			if(!dp[i][k][p] || !dp[k+1][j][q]) continue;
			int d = p*10 + q;
			for(int f = 0; f < v[d].size(); f++)
				dp[i][j][v[d][f]] = true;
		}
	}
	
	for(int i = 1; i <= 4; i++)
		if(dp[1][n][i]) cout << to[i];
	return 0;
}