hdu4545 Magic String

魔法串

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 1846    Accepted Submission(s): 692

Problem Description

　　Xiao Ming and his good friend Xiao Xi are playing a new game,A string consisting of lowercase letters is given by Konishi,Xiaoming gives another string that is longer than Xiaoxi,Also consists of lowercase letters,If you can make Xiaoming's string and Xiaoxi's become the same through magic conversion,那么他们两个人都会很开心.The magic here means that Xiaoming's string can arbitrarily delete a character,Or change some characters against the character change table.如：
　　　　Konishi's string is abba;
　　　　Xiao Ming's string is addba; 
　　　　character change table d b （表示d能转换成b）.
　　Then Xiao Ming can delete the firstd,然后将第二个d转换成bThe string into aabba.

　　Now please help to judge：Can they make the strings of two people the same through magic transformation?？

 

Input

　　首先输入T,表示总共有T组测试数据(T <= 40).
　　接下来共T组数据,Enter the string of Xiaoxi in the first line of each set of data,Enter Xiao Ming's string on the second line（The data guarantees that the string length does not exceed1000,The length of Xiaoming's string is greater than or equal to Xiaoxi's,And all characters are in lowercase）.Then enter the alphabet,先输入m,表示有mcharacter transformation（m< = 100）,接着mEnter two lowercase letters per line,Indicates that the previous one can become the next one（It doesn't mean the latter can become the former）.

 

Output

　　对于每组数据,先输出Case数.
　　If two people's strings could be made the same through magic transformation,输出“happy”,
　　否则输出“unhappy”.
　　每组数据占一行,具体输出格式参见样例.

 

Sample Input

2 abba addba 1 d b a dd 0

 

Sample Output

Case #1: happy Case #2: unhappy

 

 

Recommend

liuyiding   |   We have carefully selected several similar problems for you

 

​ ​Statistic​​ | 

​ ​Submit​​ | 

​ ​Discuss​​ | 

​ ​Note​​

classmates asked me.Changed according to her code.

登录后复制

      
      

       
       #include<stdio.h>
       
       

       
       #include<string.h>
       
       

       
       char 
       
       stra[
       
       1010],
       
       strb[
       
       1010],
       
       a[
       
       110],
       
       b[
       
       110];
       
       

       
       int 
       
       main(){
       
       
    
       
       int 
       
       t,
       
       num
       
       =
       
       0,
       
       alen,
       
       blen,
       
       m,
       
       i,
       
       j,
       
       n;
       
       
    
       
       scanf(
       
       "%d",
       
       &
       
       t);
       
       
    
       
       while(
       
       t
       
       --)
       
       
    {
       
       
        
       
       int 
       
       k
       
       =
       
       0,
       
       flag
       
       =
       
       1;
       
       
        
       
       num
       
       ++;
       
       
        
       
       memset(
       
       a,
       
       0,
       
       sizeof(
       
       a));
       
       
        
       
       memset(
       
       b,
       
       0,
       
       sizeof(
       
       b));
       
       
        
       
       scanf(
       
       "%s %s",
       
       stra,
       
       strb);    
       
       
        
       
       alen
       
       =
       
       strlen(
       
       stra); 
       
       blen
       
       =
       
       strlen(
       
       strb); 
       
       
        
       
       scanf(
       
       "%d",
       
       &
       
       m);    
       
       
        
       
       while(
       
       m
       
       --)
       
       
        {
       
       
            
       
       scanf(
       
       " %c %c",
       
       &
       
       b[
       
       k],
       
       &
       
       a[
       
       k]);  
       
       
            
       
       k
       
       ++;
       
       
        }
       
       
        
       
       int 
       
       flag2;
       
       
        
       
       for(
       
       i
       
       =
       
       0,
       
       j
       
       =
       
       0;
       
       i
       
       <
       
       alen
       
       &&
       
       j
       
       <
       
       blen;)
       
       
        {  
       
       
            
       
       flag2
       
       =
       
       0;
       
       
            
       
       if(
       
       stra[
       
       i]
       
       !=
       
       strb[
       
       j])
       
       
            {     
       
       
                
       
       for(
       
       n
       
       =
       
       0;
       
       n
       
       <
       
       k;
       
       n
       
       ++)
       
       
                {      
       
       
                    
       
       if(
       
       strb[
       
       j]
       
       ==
       
       b[
       
       n]
       
       &&
       
       stra[
       
       i]
       
       ==
       
       a[
       
       n]) 
       
       
                        {
       
       
                            
       
       i
       
       ++,
       
       j
       
       ++,
       
       flag2
       
       =
       
       1;
       
       
                            
       
       break;
       
       
                        }      
       
       
                    }
       
       
                
       
       if(
       
       !
       
       flag2)
       
       
                
       
       j
       
       ++;
       
       
           }
       
       
            
       
       else
       
       
            
       
       i
       
       ++,
       
       j
       
       ++; 
       
       
        }
       
       
        
       
       if(
       
       i
       
       ==
       
       alen) 
       
       
            
       
       printf(
       
       "Case #%d: happy\n",
       
       num); 
       
       
        
       
       else
       
       
            
       
       printf(
       
       "Case #%d: unhappy\n",
       
       num);
       
       
    }
       
       
    
       
       return 
       
       0;
       
       
}
      
      
      
      

       
       
1.
       
       
2.
       
       
3.
       
       
4.
       
       
5.
       
       
6.
       
       
7.
       
       
8.
       
       
9.
       
       
10.
       
       
11.
       
       
12.
       
       
13.
       
       
14.
       
       
15.
       
       
16.
       
       
17.
       
       
18.
       
       
19.
       
       
20.
       
       
21.
       
       
22.
       
       
23.
       
       
24.
       
       
25.
       
       
26.
       
       
27.
       
       
28.
       
       
29.
       
       
30.
       
       
31.
       
       
32.
       
       
33.
       
       
34.
       
       
35.
       
       
36.
       
       
37.
       
       
38.
       
       
39.
       
       
40.
       
       
41.
       
       
42.
       
       
43.
       
       
44.
       
       
45.
       
       
46.
       
       
47.