0

strong text

#include <iostream>
#include<set>
#include <string>
#include <string_view>
#include <boost/algorithm/string.hpp>
using std::string;
using std::cout;
using std::cin;
using std::endl;
int main() 
{
     long int t;
     cin>>t;
     while(t--)
    {
        string s1,s2,x,a,b,f;
        cin>>s1>>s2>>x;
        std::set<string> s;
        int n,m,A;
        n=s1.length();
        m=s2.length();
        for(int i=0;i<n;i++)
        {
            a=s1.substr(0,i+1);
            if(boost::algorithm::contains(x, a));
            {
                s.insert(a+"0");
            }
            for(int j=0;j<m;j++)
            {
                b=s2.substr(0,j+1);
                if(boost::algorithm::contains(x,b))
                {
                    s.insert("0"+b);
                }
                f=a+b;
                if(boost::algorithm::contains(x,f))
                {
                    s.insert(f);
                }
            }
           
        }
        cout<<(s.size())+1<<endl;
            for (auto it = s.begin(); it !=
                             s.end(); ++it)
        cout << endl << *it;
    /*A=boost::algorithm::contains(x,"aa0");
        cout<<A;*/
    }
    return 0;
}

**Given 3 strings S1, S2 and X, find the number of distinct ordered pairs of strings (P,Q) such that :

String P+Q is a substring of X.

String P is some prefix of S1 (possibly empty).

String Q is some prefix of S2 (possibly empty).

A substring of a string is a contiguous subsequence of that string. For example, "chef" is a substring of "codechef", but "def" is not. Also, an empty string is a substring of any string.

A prefix of a string S is a substring of S that occurs at the beginning of S. For example, "code" is a prefix of "codechef", but "chef" is not. Also, an empty string is a prefix of any string.**

**My approach-slicing the string s1 and s2 using substr function and then checking whether there are substring of x using a algorithm or boost function i have used s.insert(a+"0") it just signifies that a is a prefix of s1 string and we have taken null prefix i.e. "" from s2. Same s.insert(""+b) means null prefix from string s1 and b prefix from s2 and so on.

****Problem - It is giving wrong output for one inputset dont know why. Debug it and see the pic https://i.stack.imgur.com/zUm5O.png **

Abhishek Sanwal
  • 7
  • 3
  • It is giving right output for other cases. However for this case I cant code behavior. – Abhishek Sanwal Oct 19 '21 at 11:54
  • 3
    `#include ` **and** other includes from the Standard Library indicates that you are copy/pasting code without knowing what it actually does. The advice you'll get from this site is to [NOT use bits/stdc++.h](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h). You should also [not include `using namespace std;`](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice). – sweenish Oct 19 '21 at 11:56
  • I have just checking various efficient substring checking methods.I have put using namespace std after the function so std:: – Abhishek Sanwal Oct 19 '21 at 11:59
  • 3
    What you are "just" doing is writing unreadable and nigh un-debuggable code. Use proper variable names, for a start. The goal of writing code is to do so in a way that is human-readable. – sweenish Oct 19 '21 at 12:01
  • Anyone here who is going to try to help you already knows what `using namespace std;` does. And they will still tell you not to do it. I've edited my earlier comment with links as to why two lines of your code in particular are terrible practice. – sweenish Oct 19 '21 at 12:03
  • Actually usually I dont write Code in C++. I write code in Python3 Since it is giving TLE.I have switched language to C++. – Abhishek Sanwal Oct 19 '21 at 12:07
  • 2
    @AbhishekSanwal I think that when you encountered an TLE(Time Limite Exceeded), usually your implementation is slow, not the language you're using. – justANewb stands with Ukraine Oct 19 '21 at 12:10
  • To be more specific, you're using the wrong algorithm. Substring stuff usually involves a sliding window. – sweenish Oct 19 '21 at 12:16
  • Yes I agree to you at some extent .But currently no other approach in my mind regarding this ques. – Abhishek Sanwal Oct 19 '21 at 12:17
  • Add link of the algorithm that i should use. and kindly find error in this program – Abhishek Sanwal Oct 19 '21 at 12:19
  • i have used s.insert(a+"0") it just signifies that a is a prefix of s1 string and we have taken null prefix i.e. "" from s2. Same s.insert(""+b) means null prefix from string s1 and b prefix from s2 and so on. – Abhishek Sanwal Oct 19 '21 at 12:45
  • 1
    "Add link of the algorithm that i should use." No. That's not how this site works. Please read [ask] and [mre], and take the [tour]. – sweenish Oct 19 '21 at 14:08

1 Answers1

0

I cleaned up your main function a little and removed boost usage (since you don't really need it here). I've also removed your namespace declarations as that is a bad idea. Lastly, I replaced your boost usage with a simple string::find. You can find the live example here.

The output is :

4

0b
a0
ab

The updated main() is below with your example set, instead of using std::cin.

#include <iostream>
#include <set>
#include <string>

int main() 
{
     long int t{1};
     while(t--)
    {
        std::string s1{"aa"},s2{"bb"},x{"ab"},a{""},b{""},f{""};
        std::set<std::string> s;
        int n,m,A;
        n=s1.length();
        m=s2.length();
        for(int i=0;i<n;i++)
        {
            a=s1.substr(0,i+1);
            if(x.find(a) != std::string::npos)
            {
                s.insert(a+"0");
            }
            for(int j=0;j<m;j++)
            {
                b=s2.substr(0,j+1);
                if(x.find(b) != std::string::npos)
                {
                    s.insert("0"+b);
                }
                f=a+b;
                if(x.find(f) != std::string::npos)
                {
                    s.insert(f);
                }
            }
           
        }
        std::cout<<(s.size())+1<<std::endl;
            for (auto it = s.begin(); it !=
                             s.end(); ++it)
        std::cout << std::endl << *it;
    /*A=boost::algorithm::contains(x,"aa0");
        cout<<A;*/
    }
    return 0;
}
mpro34
  • 96
  • 6