11583 - Alien DNA

[Igor9669]

What need to do in this problem???
Please...

[cathy]

How is it possible to solve this problem if you get TLE just reading the input??? This program gives me TLE:

#include <iostream>
using namespace std;
#include <string>

int main()
{
long long i, n, x, nc, cuts=0;
string s;
cin >> nc;
for (x = 0; x < nc; x++) {
cin >> n;
for (i = 0; i < n; i++) {
cin >> s;
}
cout << cuts << endl;
}
return 0;
}

[Igor9669]

Don't use cin here, it is too slow....

[Chirag Chheda]

I am unable to understand this problem. Can someone please explain it to me??
Than in advance

[setu]

I am unable to understand this problem. Can someone please explain it to me??
Than in advance

Its not so hard as u thinking. Just take strings one after another and find out the common bases. Take only common bases and compare it with next string untill the common bases string is not NULL. If NULL then cut and start next string otherwise continue finding common bases among the upcoming strings.
INPUT:
asd
sdf
cd
gh

OUTPUT:
1
Becoz the only common base among the first three string is d and as we have to take least minimum cuts so we should be greedy in choosing d avoiding s in above two strings.
Am i clear to understand u?

[Chirag Chheda]

Thanx a lot 4 u reply. It was very helpful for me. I finally managed to solve it.