C++11(clang++ 3.9) 解法, 执行用时: 68ms, 内存消耗: 396K, 提交时间: 2020-07-02 16:43:17

#include <bits/stdc++.h>
using namespace std;

string a[5], b[5], s, t;
int q;
int r1[9], r2[9];
string r3[9];

bool dfs(int u, string s) {
	if (u == q) return s == t;

	for (int i = 0; i < 3; i++)
		for (int j = 0; j + a[i].size() <= s.size(); j++) {
			if (a[i] == s.substr(j, a[i].size())) {
				string w = s.substr(0, j) + b[i] + s.substr(j + a[i].size());
				if (dfs(u + 1, w)) {
					r1[u] = i + 1, r2[u] = j + 1, r3[u] = w;
					return true;
				}
			}
		}

	return false;
}

int main() {
	for (int i = 0; i < 3; i++)
		cin >> a[i] >> b[i];
	cin >> q >> s >> t;
	dfs(0, s);

	for (int i = 0; i < q; i++)
		cout << r1[i] << ' ' << r2[i] << ' ' << r3[i] << endl;
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 96ms, 内存消耗: 456K, 提交时间: 2019-12-13 23:10:32

#include<bits/stdc++.h>
using namespace std;
string a[3],b[3];
int k;string from,to;
vector<pair<pair<int,int>,string>>v;
void dfs(string now){
	if (v.size()==k){
		if (now==to){
			for (auto i:v)cout<<i.first.first<<" "<<i.first.second<<" "<<i.second<<endl;
			exit(0);
		}
		return;
	}
	for (int i=0;i<3;i++){
		int p=-1;
		while((p=now.find(a[i],p+1))!=-1){
			string temp=now;
			temp.replace(p,a[i].size(),b[i]);
			v.push_back({{i+1,p+1},temp});
			dfs(temp);
			v.pop_back();
		}
	}
}
int main(){
	for (int i=0;i<3;i++)cin>>a[i]>>b[i];
	cin>>k>>from>>to;
	dfs(from);
}