Common Permutation
时间: 1ms 内存:64M
描述:
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
提示:
参考答案(内存最优[752]):
#include<stdio.h>
#include<string.h>
int main()
{
int k,j;
char a[1000],b[1000],i;
do
{
gets(a);
gets(b);
for(i='a';i<='z';i++)
{
for(j=0;j<strlen(a);j++)
{
if(a[j]==i)
{
for(k=0;k<strlen(b);k++)
{
if(b[k]==a[j])
{
printf("%c",i);
break;
}
}
break;
}
}
}
printf("\n");
}while(scanf("%d",&a)!=EOF);
return 0;
}
参考答案(时间最优[0]):
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int a[300];
int main()
{
char c[80],d[80];
while(gets(c))
{
gets(d);
memset(a,0,sizeof(a));
for(int i=0; i<strlen(c); i++)
for(int j=0; j<strlen(d); j++)
if(c[i]==d[j])a[c[i]]++;
for(int i=65; i<130; i++)
if(a[i])printf("%c",i);
printf("\n");
}
return 0;
}
题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。