Longest common prefix

[closed account 3UohqMoL]

https://www.codechef.com/JUNE18B/problems/SHKSTR

My code

#include <bits/stdc++.h>
using namespace std;

vector<pair<int, string>> coll;

bool sortByFirst(const pair<int, string> &a, const pair<int, string> &b) {
return (a.first > b.first);
}

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;
}
}
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);
sort(coll.begin(), coll.end(), sortByFirst);
int k = coll[0].first;
string minString = coll[0].second;
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;
}

[closed account 3UohqMoL]

Can you help @lastchance
Tell me my mistake

[lastchance]

@Wasp,

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.

[closed account 3UohqMoL]

#include <bits/stdc++.h>
using namespace 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.

[jonnin]

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?

[closed account 3UohqMoL]

No its not like that @jonin the sequence of operations is correct in the code but theres some missing thats why i am getting a test case wrong

[lastchance]

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>
using namespace 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];
         }
         else if ( 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.

You can use < to compare strings, you know.

[jonnin]

clarify what is not correct with my statement?

[ashishyadav]

what is wrong with my code?

[code]#include<bits/stdc++.h>
using namespace std;
string cpu(string str1, string str2)
{
    string result;
    int n1 = str1.length(), n2 = str2.length();
 
    for (int i=0, j=0; i<=n1-1&&j<=n2-1; i++,j++)
    {
        if (str1[i] != str2[j])
            break;
        result.push_back(str1[i]);
    }
    return (result);
}
int main()
{
	int n,r,i,q;
	cin>>n;
	string s[n],p,s1,result,lcp;
	for(i=0;i<n;i++)
	cin>>s[i];
	cin>>q;
	result=s[0];
	while(q--)
	{
		s1="null";
		cin>>r>>p;
		for(i=0;i<r;i++)
		{
			lcp=cpu(s[i],p);
			if(lcp.length()>s1.length())
			{
				s1=lcp;
				result=s[i];
			 }
			 else if(lcp.length()==s1.length())
			 {
			 	if(lexicographical_compare(s[i].begin(), s[i].end(),result.begin(), result.end()))
			 	result=s[i];
			  } 
		}
		cout<<result<<endl;
	}
}

[code]

[icy1]

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.

[ashishyadav]

@icy1
you can try to understand it by taking a example

[closed account 3UohqMoL]

@kashish your code passes how many test cases?

[icy1]

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.

[ashishyadav]

@Wasp my passes 1st test case only 30 points

[icy1]

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):

#include <iostream>
#include <string>
#include <vector>

using namespace std;

// Examine v[0..index-1] for common prefix p (maximal possible)
// Return lexicographic min of these.
string Query(const vector<string>& v, int index, const string& p)
{
    // Consecutive match score and success status. Set to false when prefix
    //   letter match fails.
    static pair<int,bool> def {0, true};
    vector<pair<int,bool>> winners(index, def);
    for (int i=0; i<index; ++i)
    {
        const string& s = v[i];
        // Index for character of prefix
        for (int j=0; j<p.size(); ++j)
        {
            if (!winners[i].second)
                break;

            if (s[j] == p[j])
                winners[i].first += 1;
            else
                winners[i].second = false;
        }
    }

    // Analyze all winners with max score. Return lexicographic min of these.
    int best_index = 0;
    int max_score = winners[0].first;
    for (int i=1; i<index; ++i)
    {
        const int& score = winners[i].first;
        if (score > max_score )
        {
            max_score = score;
            best_index = i;
        }
        else if (score == max_score)
        {
            if (v[i] < v[best_index])  // lexicographic min
                best_index = i;
        }        
    }
    return v[best_index];
}

int main() 
{
    vector<string> v
    {
        "abcd", 
        "abce",
        "abcdex",
        "abcde"
    };
    cout << Query(v, 3, "abcy") << endl;   // "abcd"
    cout << Query(v, 3, "abcde") << endl;  // "abcdex"
    cout << Query(v, 4, "abcde") << endl;  // "abcde"
    
    return 0;
}

[lastchance]

icy wrote:

rip; got TLE (time limit exceeded?) without any further info after the first 30 points.

Join the club, @icy! Same with my code. I think the answers are correct: they're just taking too long to reach.

I'm afraid I can't see how to shortcut the comparisons and get the time complexity down.

Like you, I find that actually understanding the questions on the codechef site is quite an initial hurdle!

[icy1]

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.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

void QuerySearch(const vector<string>& v, int index, const string& p)
{
    // Partial list
    vector<string> plist(index);
    partial_sort_copy(v.begin(), v.begin()+index, plist.begin(), plist.end());
    int max_index = p.size();
    while (max_index--)
    {        
        string s(p.begin(), p.begin()+max_index+1);
        auto it = lower_bound(plist.begin(), plist.end(), s);
        if (it != plist.end())
        {
            cout << *it << endl;
            return;
        }
    }
}
int main() 
{
    vector<string> v
    {
        "abcd", 
        "abce",
        "abcdex",
        "abcde"
    };
    QuerySearch(v, 3, "abcy");   // "abcd"
    QuerySearch(v, 3, "abcde");  // "abcdex"
    QuerySearch(v, 4, "abcde");  // "abcde"
    
    return 0;
}

[closed account N6Xyb7Xj]

use mo's algorithm..!

[tpb]

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>
using namespace 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';
    }
}

[closed account 3UohqMoL]

@lastchange you told that we shouldn't use sorting this can help us little bit