https://community.topcoder.com/stat?c=problem_statement&pm=7415&rd=10666

文字列$str$を$resources$中の文字列から$1$つ選んで作りたい．$resources$の各文字列にある”%s”は，$resources$中の任意の文字列に置き換えすることができる．$str$を構成できる組み合わせは何通りか．

$$ \begin{eqnarray} dp[i][j] &:=& [i, j)を構成できる組み合わせ数\\
dp2[i][j][k][l] &:=& [i, j)をresources[j][l]まで見て構成できる組み合わせ数 \end{eqnarray} $$

区間$[l, r)$に各文字列を当てた場合を全て試す．’%s’が無い場合は，その区間と割り当てた文字列が完全に一致している場合は$1$，そうでない場合は$0$を返す．ある場合は，$[l, r)$区間のどこまでを$%s$で別の文字列に置き換えるか，$[l, i)$, $[i, r)$に分割する$i$を全て試す．$dp2[l][r][id][pos] += (a * b) % MOD;$にMODを入れないとoverflowする(落ちた)．

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,k,n) for(int i=k;i<(int)(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair
#define MOD 1000000007

#define fi first
#define se second

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

int n;
string s;
vector<string> v;

int dp[55][55], dp2[35][35][55][55];

ll dfs(int l, int r);
ll dfs2(int l, int r, int id, int pos);

ll dfs(int l, int r) {
	if(dp[l][r] != -1) return dp[l][r];
	dp[l][r] = 0;
	rep(i, n) {
		dp[l][r] += dfs2(l, r, i, 0);
		dp[l][r] %= MOD;
	}
	return dp[l][r];
}

ll dfs2(int l, int r, int id, int pos) {
	if(dp2[l][r][id][pos] != -1) return dp2[l][r][id][pos];
	if(pos >= v[id].size()) return 0;

	if(v[id][pos] == '?') {
		if(pos != v[id].size() - 1) {
			dp2[l][r][id][pos] = 0;
			for(int i = l + 1; i <= r; i++) {
				ll a = dfs(l, i);
				ll b = dfs2(i, r, id, pos + 1);
				dp2[l][r][id][pos] += (a * b) % MOD;
				dp2[l][r][id][pos] %= MOD;
			}
			return dp2[l][r][id][pos];
		} else {
			return dp2[l][r][id][pos] = dfs(l, r);
		}
	} else {
		if(s[l] != v[id][pos]) return 0;
		if(r - l == 1) {
			if(pos == v[id].size()-1) return 1;
			else return 0;
		}
		return dp2[l][r][id][pos] = dfs2(l + 1, r, id, pos + 1);
	}
}

class ReverseResources {
	public:
	int findDecompositions(string str, vector <string> resources) {
		s = str;
		n = resources.size();
		v.clear(); v.resize(n);
		rep(i, n) {
			string t = "";
			rep(j, resources[i].size()) {
				if(j + 1 < resources[i].size() && resources[i][j] == '%' && resources[i][j+1] == 's') {
					j++;
					t += "?";
				} else {
					t += resources[i][j];
				}
			}
			v[i] = t;
		}

		memset(dp, -1, sizeof(dp));
		memset(dp2, -1, sizeof(dp2));
		return dfs(0, s.size());
	}
};

hugo

エスケープで色々問題が起こっている．どうすればよいか