HDU 4545 魔法串
Problem Description
小明和他的好朋友小西在玩一个新的游戏，由小西给出一个由小写字母构成的字符串，小明给出另一个比小西更长的字符串，也由小写字母组成，如果能通过魔法转换使小明的串和小西的变成同一个，那么他们两个人都会很开心。这里魔法指的是小明的串可以任意删掉某个字符，或者把某些字符对照字符变化表变化。如：
小西的串是 abba;
小明的串是 addba;
字符变化表 d b （表示d能转换成b）。
那么小明可以通过删掉第一个d，然后将第二个d转换成b将串变成abba。
现在请你帮忙判断：他们能不能通过魔法转换使两个人的串变成一样呢？
Input
首先输入T，表示总共有T组测试数据(T <= 40)。
接下来共T组数据，每组数据第一行输入小西的字符串，第二行输入小明的字符串（数据保证字符串长度不超过1000，小明的串的长度大于等于小西的，且所有字符均为小写字母）。接着输入字母表，先输入m，表示有m个字符变换方式（m< = 100），接着m行每行输入两个小写字母，表示前一个可以变为后一个（但并不代表后一个能变成前一个）。
Output
对于每组数据，先输出Case数。
如果可以通过魔法转换使两个人的串变成一样，输出“happy”，
否则输出“unhappy”。
每组数据占一行，具体输出格式参见样例。
Sample Input
2
abba
addba
1
d b
a
dd
0
Sample Output
Case #1: happy
Case #2: unhappy
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1005;
int vis[30][30];
char s1[1009],s2[1009];
int main()
{
int Case,T;
scanf("%d",&T);
for(Case = 1; Case<=T; Case++)
{
memset(vis,0,sizeof(vis));
int len1,len2;
scanf("%s",s1);
scanf("%s",s2);
len1 = strlen(s1);
len2 = strlen(s2);
int n;
scanf("%d",&n);
for(int i = 0; i<n; i++)
{
char a,b;
cin>>a>>b;
vis[a-'a'][b-'a'] = 1;//将可以进行转换的字符间的关系保存下来
}
int j = 0;
int flag = 0;
for(int i=0;i<len1;i++)//要为字符串1中的每一个字符都完全匹配
{
if(j==len2)//第二个串已经结束了
{
break;
}
if(s1[i]==s2[j])//当前的两个字符证号可以匹配
{
j++;
continue;
}
int ss=0; //用于标记，如果是匹配的情况下，让字符串2下标++
while(s1[i]!=s2[j])//不能匹配的话就接着往下找
{
if(j==len2)//字符串1还没有结束，但是字符串2已经结束了
{
flag=1;//这样就肯定是不能够匹配的了
break;
}
if(vis[s2[j]-'a'][s1[i]-'a']==1)//字符串2中的当前字符可以转换为字符串1
{
j++;ss=1; //转换的情况下字符串2下标已经++
break;
}
else
{
j++;
}
}
if(ss=0) //判断是何种跳去情况
j++;
}
printf("Case #%d: ",Case);
if(!flag)
printf("happy\n");
else
printf("unhappy\n");
}
return 0;
}
虾皮信息成长空间 250人发布
