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.
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.
For each set of input, output a line containing x. If several x satisfy the criteria above, choose the first one in alphabetical order.
pretty
women
walking
down
the
street
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");
}
}
posted on 2010-03-18 09:09
付翔 阅读(374)
评论(0) 编辑 收藏 引用 所属分类:
ACM 数据结构