Longest common prefix

Pages: 12
JLBorges (13770)
If Q is large, consider using a trie. https://en.wikipedia.org/wiki/Trie
closed account N6Xyb7Xj (6)
did anyone get a better and faster algorithm to solve this problem?
qwerty1qwerty (7)
can anyone provide a solution for this question
link to the question
https://www.codechef.com/JUNE18B/problems/VSN
lastchance (6980)
OK, unequivocally have to give credit to @tpb: used a map<string,int> in the end.

No, I'm not going to explain this unholy mess, but it passed. (Change the settings for the 'in' stream to run it on codechef).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
 
#include <iostream>
#include <sstream>
#include <string>
#include <map>
#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(                   // 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;
   string P, str;
   map<string,int> S;
   map<string,int>::iterator itp, itm, it;


   // Read strings
   in >> N;
   for ( int i = 0; i < N; i++ ) 
   {
      in >> str;
      S.insert( pair<string,int>( str, i + 1 ) );
   }


   // Now deal with the queries one by one
   in >> Q;
   for ( int q = 0; q < Q; q++ )
   {
      in >> R >> P;

      // Find where P is or would be in the map (which is sorted, so longest common prefix is just before or after)
      auto found = S.find( P );
      if ( found != S.end() && found->second <= R )        // If this is already available before line R, just print it out
      {
         cout << P << '\n';
         continue;
      }
      auto ins = found;                                    // Otherwise either use current position of P ...
      if ( found == S.end() ) ins = S.insert( pair<string,int>( P, -1 ) ).first;     // ... or insert if necessary

      // Find the common prefix length on either side; the larger will be the maximum common prefix
      int LCPm = -1, LCPp= -1;
      itp = ins;
      for ( itp++; itp != S.end(); itp++ )                 // Strings after P in lexicographical order
      {
         if ( itp->second <= R )
         {
            LCPp = lengthOfCommonPrefix( itp->first, P );
            break;
         }
      }

      itm = ins;
      while ( itm != S.begin() )                           // Strings before P in lexicographical order
      {
         itm--;
         if ( itm->second <= R )
         {
            LCPm = lengthOfCommonPrefix( itm->first, P );
            break;
         }
      }

      if ( LCPp > LCPm )               // Answer is immediately after in lexicographical order
      {
         cout << itp->first << '\n';
      }
      else                             // Otherwise, work backwards to find earliest string with same common prefix
      {
         it = itm;
         while ( it != S.begin() )
         {
            it--;
            if ( it->second <= R )
            {
               if ( lengthOfCommonPrefix( it->first, P ) == LCPm ) itm = it;
               else                                                break;
            }
         }
         cout << itm->first << '\n';
      }

      if ( found == S.end() ) S.erase( P );                // You put it ... you have to take it out!
   }
}

Last edited on
qwerty1qwerty (7)
@lastchance
can you provide a solution to this question
https://www.codechef.com/JUNE18B/problems/VSN
lastchance (6980)
@qwerty1qwerty

At the moment, no - I've got to get back to work.

It's a different problem: start a new thread.
closed account 1TD80pDG (101)
@lasrchance your above code( Sheokand and String) is giving TLE for two test cases(first two test case of the second part)). how to overcome with it?. only first subtask is passed. which is I'm already done before this.

here is my code .it is give TLE for the second part of problems 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
 

#include<iostream>
#include<string.h>
 
using namespace std;
 
int main()
{
    int n;
    cin>>n;
    string str[n];
    for(int i=0; i<n; i++)
        cin>>str[i];
    
    int q;
    cin>>q;
    
    int arr[q];
    
    string str1[q];
  
    string strstr[q];
    
    
    int x=0; int xx1=0; int i_1=0;
    while(q--)
    {     
         cin>>arr[i_1];
        
         cin>>str1[i_1];
        
        int len= str1[x].length();
     
           int max_count=-1;
      
        
        
        for(int i=0; i<arr[x]; i++)
        {
            int count=0;
            
           
            for(int j=0; j<len; j++)
            {
                if(str1[x][j]==str[i][j])
                    count++;
                else 
                    break;
                
            }
            
           
            
           if(count>max_count)
           {   max_count=count;
             
           }
            
        }
        
       
        
        
         string r = str1[x].substr(0, max_count);
             
         
        
        
       int fla1=0;
        int notinter=0; int preserve,lep;
        for(int i=0; i<arr[x]; i++)
        {    
              
            
            if(str[i].compare(0,max_count, r )==0 )
            {  
                  
               
                
                  if(!fla1)
                  {   lep=str[i].length();
                     preserve=i; 
                      
                  }
             
             int len11= str[i].length();
                if(fla1)
                {   notinter=1; 
                    
                   if(lexicographical_compare(str[preserve].begin() ,str[preserve].end(), str[i].begin(),str[i].end() )  )  
                   { }
                    else
                    {
                       preserve=i;
                        lep=len11;
                    }
                    
                }
             
                fla1=1;
            }
            
        }
            
          
          cout<<str[preserve]<<endl;  
           
        xx1++;
      x++;
        
      i_1++;
        
        
        
    }
    
    
    
    
    
    
}
Last edited on
lastchance (6980)
your above code( Sheokand and String) is giving TLE for two test cases(first two test case of the second part)). how to overcome with it?. only first subtask is passed.


Actually, @ipg..., this is what it gave me. Perhaps you are putting it in incorrectly.

1		0		AC
(0.000000)	
1		1		AC
(0.000000)	
1		2		AC
(0.000000)	
Subtask Score: 30.00%		Result - AC	
2		3		AC
(0.730000)	
2		4		AC
(0.890000)	
2		5		AC
(0.390000)	
Subtask Score: 70.00%		Result - AC
closed account 1TD80pDG (101)
@lastchance, okay got it.
qwerty1qwerty (7)
@lastchance
can you help in solving this question
link to the question-:
https://www.codechef.com/JUNE18B/problems/VSN
i already created new thread for this
link to the new thread is this -:
http://www.cplusplus.com/forum/beginner/237932/
Last edited on
tpb (1495)
lastchance wrote:
unequivocally have to give credit to @tpb: used a map<string,int> in the end.

Thanks, man. Glad my buggy code could do some good!
I'll study your solution later today.
icy1 (596)
I'm still confused by some wrong answers from my code =/

Firstly, if I search for something that doesn't even have one character in common, e.g. "x" , I don't print anything. This seems to be okay because the problem didn't have any specification for this scenario. lastchance prints out the first dictionary entry, but even when I tried to print first element as a failsafe, I still got wrong answers.

I must agree with the assessment that using std::map is a wonderful idea, and we're actually making use of its built-in sorting. My latest code/test still completely depends on the lower_bound algorithm, and I'm thinking that there's no need to iterate back towards beginning, because the result of the lower_bound call is already perfect. I chop off characters from the back of prefix incrementally, so if called with a 6-letter prefix, I search the full 6 letters, then indices [0..4], inclusive, [0..3], inclusive, etc.

For submission, everything now runs within the 1sec time constraint, and I now get
Wrong
Right
Right
-----
Wrong
Wrong
Right


My latest code w/ tests looks like [below]. I'm having trouble finding examples that create wrong answers -- can someone help come up with tricky dictionary and queries?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
 
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>

// 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.
//
// More details on input/output
// https://www.codechef.com/JUNE18B/problems/SHKSTR

using namespace std;

bool IsPrefix(const string& p, const string& s)
{
    return p.size()<=s.size() &&
           equal(p.begin(), p.begin()+p.size(), s.begin());
}

void QuerySearch(const map<string,int>& m, int index, const string& prefix)
{
    int psize = prefix.size();
    bool next_prefix;
    string p;
    while (psize--)
    {
        // Keep chopping last character
        p.assign(prefix, 0, psize+1);
        next_prefix = false;
        //cout << "  p: "<< p << endl;
        auto it = m.lower_bound(p);
        if (it != m.end())
        {
            //cout << "    iterator currently set at word "<<it->first<< endl;
            // Position was beyond scope of index, but answer should be nearby
            while (it->second >= index)
            {
                ++it;
                if (it==m.end())
                {
                    next_prefix = true;
                    break;
                }                
            }
            if (next_prefix)
                continue;
            
            if (IsPrefix(p, it->first))
            {
                cout << it->first << endl;
                //cout << it->first << "   " << it->second << endl;
                return;
            }
        }
    }
    // Possible default response if not even one letter matches
    //cout << "----" << endl;
}

void Show(const pair<string,int>& kv)
{
    cout << kv.first << " => " << kv.second << endl;
}

void Show(const map<string,int>& m)
{
    for (auto& kv : m)
        Show(kv);
    cout << endl;
}

int main() 
{
    // Ordered map so that it's inherently sorted but remembers its real "index"
    map<string,int> m
    {
        {"abcd",0},
        {"abce",1},
        {"abcdex",2},
        {"abcde",3},        
        {"atttttack", 4},
        {"atttttend", 5},
        {"atttttention", 6},
        {"atttttraction", 7},
        
        
    };
    cout << "Ordered Map:\n";
    Show(m);

    vector<pair<int,string>> queries
    {
        {3, "abcy"},
        {3, "abcde"},
        {4, "abcde"},

        {9, "atttttf"},
        {9, "atttttel"},
        {4, "atttttf"},
        {5, "atttttel"},    
    };

    cout << "Queries and Responses:\n\n";
    for (auto& query : queries)
    {
        cout << "{" << query.first << ", " << query.second << "}\n";
        QuerySearch(m, query.first, query.second);
        cout << endl;
    }
    
    return 0;
}


Ordered Map:
abcd => 0
abcde => 3
abcdex => 2
abce => 1
atttttack => 4
atttttend => 5
atttttention => 6
atttttraction => 7

Queries and Responses:

{3, abcy}
abcd

{3, abcde}
abcdex

{4, abcde}
abcde

{9, atttttf}
atttttack

{9, atttttel}
atttttend

{4, atttttf}
abcd

{5, atttttel}
atttttack

Last edited on
ashishyadav (46)
can someone help me in solving this problem using trie?
dragon hunter (1)
Sort the queries according to 'r' (Maintain a struct. You will need the original order later while printing).
Loop over all queries.
Keep on inserting the input strings into trie, in the original order, until next 'r', and then search the query string.
Trie building code is easy. For search, you will have to think slightly more as you gotta print the lexicographically smallest string which has longest common prefix.
closed account j8MNvCM9 (13)
Anyone getting an AC on all test cases?
Can anyone of you share your technique to get all correct?(I mean how can I avoid TLE on original constraints)?
pankajcoder (1)
@lastchance

The code is giving TLE on 5th test case (1.010000 s).
amishra31 (1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
 
#include<iostream>
#include<bits/stdc++.h>
#include<stdio.h>
using namespace std;
int main()
{
int n,i,q,r,j,large;
char str[100000][10],p[100],temp[10];
cin>>n;
for(i=0;i<n;i++)
{
cin>>str[i];
}
cin>>q;
while(q--)
{
char temp1[100000][10]={'\0'};
int counter[10]={0};
cin>>r>>p;
for(i=0;i<r;i++)
{
for(j=0;p[j]!='\0';j++)
{
if(str[i][j]!=p[j])
break;
else
counter[i]++;
}
}
large=0;
for(i=0;i<r;i++)
{
if(counter[i]>=large)
large=counter[i];
}
int m=0;
for(i=0;i<r;i++)
{
if(counter[i]==large)
strcpy(temp1[m++],str[i]);
}
for(i=0;i<m-1;i++)
for(j=i+1;j<m;j++)
{
if(strcmp(temp1[i],temp1[j])>0)
{
strcpy(temp,temp1[i]);
strcpy(temp1[i],temp1[j]);
strcpy(temp1[j],temp);
}
}
cout<<temp1[0]<<endl;
}
}


I get one AC in test case #0 while the other 2 give me WA. Getting TLE for original constraints. I know the code isn't very efficient but what all cases will fail in the above code? Any logical error? Help would be appreciated.

Also apologies for the indentation. Got messed up while copying.
Last edited on
Maanas (4)
@kashish I tried solving the question using trie. It passed all the test cases in the subtask and also two test cases with the original constraints but it gave TLE in one of the test cases in the original constraints. I can share my code if u wish.
Ihavenoname (5)
@Maanas, how are you managing the queries using a Trie? You insert it into the Trie as well, and then find out the LCP? OR, you linearly traverse the query string, and look for the LCP in the Trie? OR, something like that?
Just share the idea or a bit of the logic. I will write the code myself.
Maanas (4)
@ihavenoname, ihave sorted the queries according to R and and keep on inserting the string into the trie, once the no of strings inserted becomes equal to R, I search the trie for String mentioned in the query.
Topic archived. No new replies allowed.
Pages: 12