10252 - Common Permutation

[the LA-Z-BOy]

one of the main reason of not getting accepted is the input of blank lines...

Input file contains several lines of input. Consecutive two lines make a set of input. That means in the input file line 1 and 2 is a set of input, line 3 and 4 is a set of input and so on.

so the input might well look like...

Code: Select all

abc

efg


ghi

and output is obvious, three newline characters...

Code: Select all

Greetings

[Taneem]

Thanks a lot La-Z-Boy. I should have paid attention to that clause. I got AC (finally).

I appreciate your help.

[hujialie]

I think this problem has some mistakes in statement.

In the problem:
It says:

Each string is on a separate line and consists of at most 1000 lowercase letters

But when I used scanf("%s") to read input and just considered the lowercase letters,I got wrong answer.
Then I changed to all ASCII characters and used gets() ,eventually I got accepted.

So the statement is incorrect.

[b3yours3lf]

if I have input

pretty woman
walking down

what is the output?


thanks.

[Nick]

There are blank characters in the input and also maybe uppercase letters, which to be sorted alphabetically

Read previous post about this

input

prettywoman
walkingdown
inging
singing

the output should be

anow
ggiinn

[Larry]

Well, it *could* be a LCS.. but that's the same as using dynamic program when greedy would do.. (overkill)...

[b3yours3lf]

uppercase letter?
so if the output is aC what should I print?
aC or Ca ?

[Larry]

Given two strings of lowercase letters, a and b, print the longest string x of lowercase 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.

[Nick]

read about the previous post by hujialie...
I was getting WA when i use ASCII comparison...and when I consider the alphabetic order i got AC

input
Ca
Ca

the output should

aC

[Larry]

I used tolower and return

Code: Select all

ac

and:

Code: Select all

aaAAaaAAAa
aaAAaaAAAa

returns:

Code: Select all

aaaaaaaaaa

and still AC.

[Miguel Correia Ricardo]

What's wrong with my code?
It passes all the test i've seen in the bulletin board...

[cpp]
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

void permutation(string& a, string& b, string& result){
for (unsigned int i = 0; i < a.length(); i++)
if ((b.find(a) != string::npos))
result +=a;

sort(result.begin(), result.end());
}

int main(){
string a;
string b;
string result;
cin.setf(ios::skipws);

while(getline(cin, a) && getline(cin, b)){
permutation(a,b, result);
cout << result << endl;
a.erase();
b.erase();
result.erase();
}

return 0;
}


[/cpp]

Thank you to all that can help me

[Miguel Correia Ricardo]

Hi, i've donne some corrections, but still it gives me WA, but why...

[cpp]
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main(){
string a;
string b;
string result;

cin.setf(ios::skipws);

while(cin >> a >> b){
result.resize(1000);

transform(a.begin(), a.end(), a.begin(), tolower);
transform(b.begin(), b.end(), b.begin(), tolower);
sort(a.begin(), a.end());
sort(b.begin(), b.end());

set_intersection(a.begin(), a.end(), b.begin(), b.end(), result.begin());

cout << result << endl;

a.erase();
b.erase();
result.erase();
}

return 0;
}

[/cpp]

[Daredevil]

Mine gives WA too. Here's my code:

[c]
#include<stdio.h>
#include<string.h>
int i,min,s[30],s1[30];
char a[1002],b[1002];
void main(){
while(scanf("%s %s",&a,&b)==2){
memset(s,0,sizeof(s));
memset(s1,0,sizeof(s1));
for(i=strlen(a)-1;i>=0;i--) s[a-97]++;
for(i=strlen(b)-1;i>=0;i--) s1[b-97]++;
for(i=0;i<26;i++){
if(s&&s1){
min=s;
if(min>s1) min=s1;
while(min){
printf("%c",i+97);
min--;
}
}
}
printf("\n");
}
}
[/c]

Can anybody tell me what's wrong?
Thanx in advance!!

[Joseph Kurniawan]

Yeah, I got the same problem like you. But after I change scanf("%s"); with gets();, I got AC. Apparently each string doesn't only contain lowercase letter. The problem didn't mention this!!!

[BiK]

Although there is a much simpler solution to this problem I also started solving it with Longest Common Subsequence algorithm. On my computer it works perfectly OK producing the write answer of tons of input. But the OJ says WA.

The simpler solution is accepted only if you process the input reading lines. It seems that the judge's input data is incorrect.

DID ANYBODY OF YOU GET ACCEPTED USING THE LCS ALGORITHM?