動的計画法によって、ある \(1\) 文字 \(c\) から、\(T\) の部分文字列 \(T_iT_{i+1}\ldots T_j\) を作るのに必要な最小コスト\(dp[i][j][c]\) (不可能な場合は \(+\infty\) ) を求める事を考えます。
さらに、これを求めるために別の動的計画法を同時に回します。 それは、\(A_k\) の先頭 \(l\) 文字 \(A_{k,1}\ldots A_{k,l}\) から \(T_iT_{i+1}\ldots T_j\) を作るのに必要な最小コスト\(dp'[i][j][k][l]\) (不可能な場合は \(+\infty\) ) を求めるものです。

\(i\)について \(i=N,N-1,\ldots,1\)、\(j\) について \(j=i,i+1,\ldots,N\) の順でループを回し、\(dp'[i][j][k][l]\) \((l>1)\) \(\to\) \(dp[i][j][c], dp'[i][j][k][1]\) の順で求めていきます。

ここで、\(dp'[i_0][j_0][k][l]\) を求めようとする時点で、任意の\(i_0\leq j\leq j_0-1\)について\(dp'[i_0][j][k][l]\)、および \(i_0<i\leq j\leq N\) について \(dp[i][j][c]\) が求まっていることに注意します。 \(dp'[i][j][k][l]\)の定め方から、値は \(\displaystyle\min_{i_0\leq m\leq j_0-1} dp'[i_0][m][k][l-1]+dp[m+1][j_0][A_{k,l}]\) で求める事ができます。ここで、各操作において\(|C_k|=1\)であることから、\(A_{k,l}\)が \(T_iT_{i+1}\ldots T_j\)の後ろから何文字分に置き換えられたかというのがちゃんと定まるという事を用いています。

次に、\(dp[i][j][c], dp'[i][j][k][1]\) についてです。 \(dp[i][j][c]\) は\(i=j\)かつ\(T_i=c\)ならば\(dp[i][j][c]=1\), そうでないとき\(C_k=c\) であるような \(k\) について、\(\displaystyle\min_{C_k=c} (dp'[i][j][k][|A_k|]+1)\) で求まります。

\(|A_k|>1\)のものについてはすでに求まっているため、これらは \(dp[i][j][c]=\min (M[i][j][c], dp[i][j][d_{c,1}]+1, dp[i][j][d_{c,2}]+1,\ldots, dp[i][j][d_{c,k_c}]+1)\) として書くことができます。 ここで、\(M[i][j][c]=\displaystyle\min_{C_k=c, |A_k|>1} (dp'[i][j][k][|A_k|]+1)\) であり、\(\{d_{c,m}\}\)は\(C_k=c, |A_k|=1\) であるような\(k\)についての\(A_k\)の集合の要素です。

この部分についてはダイクストラ法を用いて解くことができます。 仮想頂点 \(V\) から頂点 \(c\) に対してコスト \(M[i][j][c]\) の辺を張ります。さらに、頂点 \(d_{c,m}\) から 頂点 \(c\) に向けてコスト \(1\) の辺を張ります。このときの頂点 \(V\) から各頂点への最小コストが\(dp[i][j][c]\)の値となります。

\(dp'[i][j][k][1]\)については、\(dp'[i][j][k][1]=dp[i][j][A_{k,1}]\)で定まります。

あとは、\(dp'[1][N][k][A_k]\) を求めたのと同様にして\(S\)から\(T\) を作るのに必要な最小コストを計算することができます。 例えば、\(i=1\) のループの時のみ \(A_{k+1}=S\), \(C_{k+1}=*\) (どのアルファベットとも異なる文字)として、追加してあげればよいです。

さて、計算量について、各 \(i,j\) について\(dp'[i][j][k][l]\)を求めるのに \(O(KN\max(|A_i|))\), その後に\(O((K+L)\log L)\) (ただし, アルファベットの文字数を\(L\)とした )よって, 全体計算量は \(O(N^3K\max(|A_i|)+N^2(K+L)\log L)\)ですが, \(N\leq 50\), \(K\leq 50\), \(\max(|A_i|)\leq 50\), \(L\leq 26\) であることから\(50^5\simeq 3\cdot 10^8\) で抑えられ, 実際の計算では (実装方針によりますが) \(\frac{1}{12}\sim\frac{1}{6}\) 程度の係数が付く事から十分間に合います。 よって、この問題を解くことができました。

なお、実現可能な場合は必要な操作回数は高々 \((L-1)(1+2+\cdots +N)+(N-1)<32000\) 回程度で抑えられるため、int型による計算で十分です。

#include <bits/stdc++.h>
using namespace std;
#define N 51
#define INF (int)1e+9
#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep2(i, a, b) for(int i = a; i <= b; ++i)
#define rep3(i, a, b) for(int i = a; i >= b; --i)
int main() {
	int n, m, k;
	string s, t;
	string c[N], a[N];
	int len[N];
	int dp1[N][N][26];
	int dp[N][N][N];
	vector<int>e[26];
	priority_queue<pair<int, int> >pq;
	pair<int, int>p;
	int sz[26];
	int x;
	cin >> s;
	cin >> t;
	cin >> k;
	rep(i, k) {
		cin >> c[i] >> a[i];
		len[i] = a[i].size();
		if (len[i] == 1)e[a[i][0] - 'a'].push_back(c[i][0] - 'a');
	}
	rep(i, 26)sz[i] = e[i].size();
	n = t.size();
	rep(i, n)rep2(j, i, n - 1)rep(ii, 26)dp1[i][j][ii] = INF;
	rep3(i, n - 1, 0) {
		rep2(j, i, n - 1)rep(ii, k)rep(jj, len[ii])dp[j][ii][jj] = INF;
		rep2(j, i, n - 1) {
			if (j == i) {
				dp1[i][j][t[j] - 'a'] = 0;
				pq.push({ 0,t[j] - 'a' });
			}
			else {
				rep(ii, k) {
					rep2(jj, 1, len[ii] - 1) {
						rep2(kk, i, j - 1) {
							if ((dp[kk][ii][jj - 1] < INF) && (dp1[kk + 1][j][a[ii][jj] - 'a'] < INF)) {
								dp[j][ii][jj] = min(dp[j][ii][jj], dp[kk][ii][jj - 1] + dp1[kk + 1][j][a[ii][jj] - 'a']);
							}
						}
					}
					if (dp[j][ii][len[ii] - 1] + 1 < dp1[i][j][c[ii][0] - 'a']) {
						dp1[i][j][c[ii][0] - 'a'] = dp[j][ii][len[ii] - 1] + 1;
						pq.push({ -dp1[i][j][c[ii][0] - 'a'],c[ii][0] - 'a' });
					}
				}
			}
			while (!pq.empty()) {
				p = pq.top();
				pq.pop();
				if (p.first == -dp1[i][j][p.second]) {
					x = p.second;
					rep(ii, sz[x]) {
						if (dp1[i][j][x] + 1 < dp1[i][j][e[x][ii]]) {
							dp1[i][j][e[x][ii]] = dp1[i][j][x] + 1;
							pq.push({ -dp1[i][j][e[x][ii]],e[x][ii] });
						}
					}
				}
			}
			rep(ii, k)dp[j][ii][0] = dp1[i][j][a[ii][0] - 'a'];
		}
	}
	m = s.size();
	rep(i, n + 1)rep(jj, m + 1)dp[i][k][jj] = INF;
	dp[0][k][0] = 0;
	rep(i, n) {
		rep(jj, m) {
			rep(j, i + 1) {
				dp[i + 1][k][jj + 1] = min(dp[i + 1][k][jj + 1], dp[j][k][jj] + dp1[j][i][s[jj] - 'a']);
			}
		}
	}
	if (dp[n][k][m] == INF)cout << -1 << endl;
	else cout << dp[n][k][m] << endl;
	return 0;
}