SKMP - Editorial


CLICK this also work

Try this test case
1
aaabbbdddd
ddab
Your Output : aaddabbbdd
Correct Output : aabbddabdd

1 Like

Can anyone please tell me Why this code was giving me wrong answers? I’m new in competitive programming, so i am unable to find the errror in my code :slight_smile:
https://www.codechef.com/viewsolution/36714426

can u plzz tell me in which case this code would give wrong output.
https://www.codechef.com/viewsolution/36779153

hey can u plzz tell in which case my answer is coming worng because i hv checked many cases and there it is giving correct output.
https://www.codechef.com/viewsolution/36779153

Bro Thank you so much I understood the problem.

Try this
1
aaabbbdddd
ddab

Your Output : aabbddddab
Correct Output : aabbddabdd

1 Like

I am not able to understand the idea used in your code but its pretty awesome
coz author, editorialist & testers solution is in contrast with your code

This means that you are reasoning in some another way
Pls share what idea are you using?
This code is passing 90% test cases.
I have exhausted with all my test cases but its giving AC in all my test case,

Very nicely explained. however, my approach is also similar. Can you please tell me Why this code was giving me wrong answers? I’m new in competitive programming, so please can u help me? :slight_smile:
https://www.codechef.com/viewsolution/36714426

Here i have three potential test cases(so that if anyone is stuck & thinks , 'in which test case my code’s lagging’ ),
If they pass then you probably will past all test case…
Sample input
3
ppq ss stx
stx
ppq sa stx
sa
ppq sz stx
sz
Sample output
ppq ss s tx
ppq sa s tx
ppq s sz tx

Ignore the spaces in they are just for convenience.

Hint 1

Do not care about “ppq” and “tx”

Hint 2

Focus on s :smile:

I am not an expert , just sharing my understanding of the question here

Can u tell me why my code is not working…

#include<bits/stdc++.h>
#include
#include<string.h>
using namespace std;
int main()
{
int t,l,l1,i,j=0,l2,k=0,x=0;
string s,p,s2,p1;
cin>>t;
while(t–)
{
s2.clear();
cin>>s;
cin>>p;
l=s.length();
l1=p.length();
p1.assign§;
sort(s.begin(),s.end());
sort(p1.begin(),p1.end());
for(i=0;i<l1;i++)
{
while(j<l)
{
if(s[j]!=p1[i])
{
s2+=s[j];
j++;
}
else
{
j++;
break;
}
}
}
if(j<l)
{
while(j<l)
{
s2+=s[j];
j++;
}
}
l2=s2.length();
for(i=0;i<l;i++)
{
if(s2[i]>=p[0])
break;
}
if(s2[i]!=p[0])
{
s2.insert(i,p);
cout<<s2<<endl;
}
else
{
k=i;
for(j=0;j<l1;j++)
{
if((p[j]>s2[k])&&(s2[k]==p[0]))
{
x++;
break;
}
else
{
k++;
}
}
if(x>0)
{
for(j=i+1;j<l2;j++)
{
if(s2[j]!=s2[i])
break;
}
s2.insert(j,p);
cout<<s2<<endl;
}
else
{
s2.insert(i,p);
cout<<s2<<endl;
}
}
j=0;
x=0;
}
return 0;
}

My python solution CodeChef: Practical coding for everyone

Can someone please explain me this line "For example: If SSS is equal to “bab” and PPP is equal to “ba” then TTT should be “abb” "?

I tried to solve this problem but looks like I have a different understanding of lexicographically shortest strings.

1 Like

Can someone please help me understand what I did wrong here??

#include
#include
using namespace std;

#define MAX 100009

int main() {
int t, idx;
char s[MAX], p[MAX], alpha[] = “abcdefghijklmnopqrstuvwxyz”;

cin>>t;

while(t--){
    
    map<char, int> mci;
    
    cin>>s>>p;
    
    for(int i=0; s[i]!='\0'; i++)
        mci[s[i]]++;
        
  for(int i=0; p[i]!='\0'; i++){
      if(mci[p[i]]>0)
        mci[p[i]]--;
  }
    
    idx = 0;
   for(; idx<26 && alpha[idx]<=p[0]; idx++){
       while(mci[alpha[idx]]--)
        cout<<alpha[idx];
   } 
   for(int i=0; p[i]!='\0'; i++)
        cout<<p[i];
   
   for(; idx<26; idx++){
       while(mci[alpha[idx]]--){
           cout<<alpha[idx];
       }
   } 
    cout<<endl;
}

return 0;

}

Thanks in advance!

I think there is a typo. The third output must be ppqssztx.

1 Like

Share your code with proper indentation or else share the link to your solution( If it is properly indented). It’s really difficult to debug this.

Here is the link to the solution. Please let me know if you can access it or not. CodeChef: Practical coding for everyone

U must check this Case : s=“abciiixaabb” p=“iax” ,
According to your code answer is : “aabbbciiiax” ,
But the answer should be : “aabbbciaxii” !

No, TTT should be bab …
Yes Its correct that we have to find lexicographically smallest answer but atleast patten should be present in that …In your answer “abb” pattern “ba” is not present .
Hope you got that .

1 Like

This is another logic I had tried and gives the exact output as you had mentioned. But, this too gave wrong answer for all the cases. CodeChef: Practical coding for everyone