Common Permutation

Given two strings a and b, print the longest string x of letters such that there is a permutation of x that is a subsequence of a and there is a permutation of x that is a subsequence of b.

Input

The input file contains several cases, each case consisting of two consecutive lines. This means that lines 1 and 2 are a test case, lines 3 and 4 are another test case, and so on. Each line contains one string of lowercase characters, with first line of a pair denoting a and the second denoting b. Each string consists of at most 1,000 characters.

Output

For each set of input, output a line containing x. If several x satisfy the criteria above, choose the first one in alphabetical order.

Sample Input

pretty
women
walking
down
the
street

Sample Output

e
nw
et

求两个字符串的公共部分  排序后即可得出 

my code
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int cmp(const void *a,const void *b)
{
    if((*(char*)a  - *(char*)b)>0)
        return 1;
    return -1;
}

int main()
{

    char str1[1005];
    char str2[1005];
    int len1,len2,i,k,x,y;
    while(gets(str1))
    {
        //if(gets(str1)==NULL)
            //break;
        gets(str2);
        
        len1 = strlen(str1);
        len2 = strlen(str2);
        qsort(str1,strlen(str1),sizeof(str1[0]),cmp);
        qsort(str2,strlen(str2),sizeof(str2[0]),cmp);
        
        //k = (len1-len2)?len1:len2;
        k = (len1>len2)?len1:len2;
        //for(x=0,y=0,i = 0;i <k;i++ ) 这样写 会提前跳出循环 一定要加强逻辑的训练 找出那些条件才是循环的控制点
        x=0,y=0;
        while((x<len1)&&(y<len2))
        {
            if(str1[x]==str2[y])
            {
                printf("%c",str1[x]);
                x++;y++;
            }
            else if(str1[x]>str2[y])
                y++;
            else
                x++;

            //if((x>=len1)||(y>=len2))
            //if((x>len1)&&(y>len2))
            //    break;
        }
        printf("\n");

    }
}