Please put your code in code tags so that we can read it properly (and try it out online).
You can either select it and use the <> option in the formatting menu or manually put [code] and [/code] tags around it.
You should also use standard headers.
Tell me my mistake
Tell us what happens when you run your code. Does it compile? Does it crash? Does it produce wrong results? We aren't psychic.
Given the names of your variables and lack of comments you had better add a description of what you are trying to do at the same time.
If you are interested in meeting time constraints then I can tell you immediately that you should be avoiding any sorting. Update the optimal result on a single pass.
#include <bits/stdc++.h>
usingnamespace std;
vector<pair<int, string>> coll;
// Sorting by first element of the pair
bool sortByFirst(const pair<int, string> &a, const pair<int, string> &b) {
return (a.first > b.first);
}
//Checking for longest common prefix of a string with given string P
void checkString(vector<string> &v, int r, string s) {
int counter = 0;
for (int i = 0; i < r; ++i) {
for (int j = 0; j < min(v[i].length(), s.length()); ++j) {
if (v[i].at(j) == s[j]) {
++counter;
} else {
break;
}
}
//Storing length of Common prefix and the String
coll.push_back(make_pair(counter, v[i]));
counter = 0;
}
}
int main() {
int n;
int r;
int i;
string p;
int queries;
cin >> n;
vector<string> v;
for (i = 0; i < n; ++i) {
cin >> p;
v.push_back(p);
}
cin >> queries;
for (i = 0; i < queries; ++i) {
cin >> r >> p;
checkString(v, r, p);
// Sorting for longest length of common prefix
sort(coll.begin(), coll.end(), sortByFirst);
int k = coll[0].first;
string minString = coll[0].second;
//Checking all strings that have Common prefix with max length
for (int j = 1; j < coll.size(); ++j) {
if (coll[j].first == k) {
if (coll[j].second.length() == minString.length()) {
if (!lexicographical_compare(minString.begin(), minString.end(), coll[j].second.begin(), coll[j].second.end())) {
minString = coll[j].second;
}
} else {
if (coll[j].second.length() < minString.length()) {
minString = coll[j].second;
}
}
} else {
break;
}
}
cout << minString << endl;
coll.clear();
}
return 0;
}
Yes, my code compiles.It only prints wrong output for 1 case.I don't know what it is.
I am not yet interested in time constraints.Thanks.
I don't see an error, but tell me what I am missing here:
get list of strings into container (if appropriate, upcase or downcase them)
sort container
check first and last element. The longest common prefix between those two is common across all of them, right?
This is O(N^2) (or at least O(N.Q) in this instance), so it will probably be way beyond the allowed time limit. I hope it will clarify the problem though.
Any suggestions as to how to improve that time complexity gratefully received.
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <algorithm>
usingnamespace std;
//=====================================================================
int lengthOfCommonPrefix( string A, string B )
{
int result = 0;
int length = min( A.size(), B.size() );
while ( result < length && A[result] == B[result] ) result++;
return result;
}
//=====================================================================
int main()
{
// istream &in = cin; // Use this for actual input
stringstream in( // Alternative version for testing
"4 \n""abcd \n""abce \n""abcdex \n""abcde \n""3 \n""3 abcy \n""3 abcde \n""4 abcde \n"
);
int N, Q, R, maxCP;
string P, best;
in >> N;
vector<string> S(N);
// Read strings
for ( int i = 0; i < N; i++ ) in >> S[i];
// Now deal with the queries one by one
in >> Q;
for ( int q = 0; q < Q; q++ )
{
in >> R >> P;
maxCP = lengthOfCommonPrefix( S[0], P );
best = S[0];
for ( int i = 1; i < R; i++ )
{
if ( S[i].size() < maxCP ) continue;
int CP = lengthOfCommonPrefix( S[i], P );
if ( CP > maxCP )
{
maxCP = CP;
best = S[i];
}
elseif ( CP == maxCP )
{
if ( S[i] < best ) best = S[i];
}
}
cout << best << '\n';
}
}
@Wasp - can you tell us which case your code is failing on? It is very complex.
I think I've read the problem from the link 5 times and am still confused. Why is it written in such a complicated manner...? This must be part of the appeal, lol.
I think I understand it now. Would've been easier if worded with a lot less variables.
For a list of strings, there will be several queries of the form "i p".
Examine list[0..i-1] against p to find all strings with maximum common prefix with p.
Return the lexicographic min of these strings.
As it was written, if feels wayyyy too math-y and not so friendly for general audience.
rip; got TLE (time limit exceeded?) without any further info after the first 30 points. Site doesn't seem too informative, though I only just made an account.
This was my simple version (before the input tweaks):
Tried a partial_sort combined with binary search approach, but I must've messed up somewhere. As I understood it, lower_bound can do most of the work for me.
The simple case looks correct, but getting Wrong Answer in whatever mysterious simple test harness they're using, and still a TLE on the harder set. le sigh.
This gets WRONG, RIGHT, RIGHT; WRONG, WRONG, RIGHT.
I'm can't figure out what's wrong with it.
But it seems fast enough, although it's hard to tell with half wrong answers.
The idea is to use a map (balanced binary tree) to hold all the words and their position in the input list. Then when searching for a prefix, it starts by finding the lower bound of just the first letter, then the first two letters, etc., until it fails (finds something that isn't actually a prefix match). It then does a linear search from the last match (or the beginning if there were no matches even for a single char) until it finds the first acceptable word position (less than R).
#include <iostream>
#include <string>
#include <map>
usingnamespace std;
int main() {
map<string, int> m;
char line[16], P[16];
int N, Q, R;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> line;
m.insert(make_pair(line, i));
}
cin >> Q;
for (int i = 0; i < Q; i++) {
cin >> R >> P;
char str[16] {P[0]}; // start with just the first letter
auto it = m.lower_bound(str);
if (it == m.end() || it->first[0] > str[0])
it = m.begin();
else {
// find longer and longer prefix matches
for (int j = 1; P[j]; j++) {
str[j] = P[j]; // add a letter
auto it2 = m.lower_bound(str);
if (it2 == m.end() || it2->first.compare(0, j+1, str) > 0)
break;
it = it2;
}
}
while (it != m.end() && it->second >= R) ++it;
if (it != m.end()) cout << it->first;
cout << '\n';
}
}