CODEWITHSUNDEEP
c++stringalgorithmfindsubstring
Sindhuja C S
Sindhuja C S

Reputation: 45

To check if there is a common substring in 2 strings c++

I've already made a solution, but I need an optimised solution. The task is to:

  1. Read two strings
  2. Get every substring of the 1st string and find each of them in the second
  3. If it exists, print "yes" or else print "no"

The solution I've already made:

int check(string A, string B)
{ 
    string s3;
    int flag=0 ,len1,len2,k=0;
    s3[0]='\0';
    cin>>A>>B;
    len1=A.length();
    len2=B.length();

    for(int i=0;i<len1;i++)
    {
        k=len1-i;

        for(int j=1;j<k;j++ )
        {
            s3=A.substr(i,j);

            size_t found=B.find(s3);

            if(found!=string::npos)
            { 
                flag=1;
                return flag;
            }

        } 
    }
}

Upvotes: 3

Views: 3594

Answers (3)

gen-y-s
gen-y-s

Reputation: 881

Put all characters of the first string into a hash set (unordered_set), then iterate on characters of second string and check if any of them exist in the hash set. If so, then there exists a common substring (of length 1 at least) otherwise, there is no common substring.

Upvotes: 1

V. Kravchenko
V. Kravchenko

Reputation: 1904

bool check(const std::string & a, const std::string & b) {
   return b.find_first_of(a) != std::string::npos;
}

You see, if string b doesn't contain a substring with size 1 from a it just can't contain a larger substring beginning with the same symbol. So you just basically need to check if string b contains any symbol from string a.

Upvotes: 1

bashrc
bashrc

Reputation: 4835

Your code has other issues besides optimized solution. For eg not all code paths return a value.

The most efficient solution depends on number of factors including the size of the two strings, how much the two strings match etc.

In absence of these information I propose that you could either use:

  1. Create a trie from the second string
  2. Create a suffix array from the first string
  3. Generate all substrings of 2nd string using suffix array. Along with generation check for its existence in the trie created in step 1.

Other approaches that you can consider includes modifying rabin karp which shouldn't be very hard to figure out.

Upvotes: 1

Related Questions