思路：对于每个字符，如果它能被替换一定要优先替换，其次再进行删除。遵循这个策略即可。
证明：
对于这题的第一个测试数据：
abba addba 1 d b
当匹配到'b' 和 'd'时应该优先替换而不是删除'd'，这样可以保证不删除掉有用的字符。
AC代码
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <utility>
#include <string>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define eps 1e-10
#define inf 0x3f3f3f3f
#define PI pair<int, int>
typedef long long LL;
typedef vector<char> v;
const int maxn = 1000 + 5;
map<char, v>ha;
char a[maxn], b[maxn];
int main() {
int T, n, m, k, kase = 1;
scanf("%d", &T);
while(T--) {
ha.clear();
scanf("%s%s", a, b);
scanf("%d", &k);
getchar();
char x, y;
for(int i = 0; i < k; ++i) {
scanf("%c %c", &x, &y);
getchar();
ha[x].push_back(y);
}
printf("Case #%d: ", kase++);
n = strlen(a), m = strlen(b);
int flag = 0, i, j;
for(i = 0, j = 0; i < n && j < m; ++j) {
if(a[i] != b[j]) {
int ok = 0;
v &u = ha[b[j]];
for(int h = 0; h < u.size(); ++h) {
if(u[h] == a[i]) {
ok = 1;
break;
}
}
if(ok) ++i;
}
else if(a[i] == b[j]) ++i;
}
if(j <= m && i == n) flag = 1;
if(flag) printf("happy\n");
else printf("unhappy\n");
}
return 0;
}
如有不当之处欢迎指出！