CODEWITHSUNDEEP
c++string
Sahil Dhawan
Sahil Dhawan

Reputation: 91

Finding no.of times small string is in large string (c++)

I have to implement c++ code to find out the number of occurrences of a small string in a large string with overlapping allowed. For eg- if large string is acacab and small string is aca, then answer should be 2. I'm not getting correct answer by making this code:

 #include<iostream>
 #include<cstring>
 using namespace std;
 int main()
 {
  int i, j, k, c=0;
  char lstr[30],sstr[10],tstr[10];
  cout<<"Enter large string:"<<endl;
  cin>>lstr;
  cout<<"Enter small string:"<<endl;
  cin>>sstr;
  for(i=0;i<strlen(lstr);i++)
  {
    if(lstr[i]==sstr[0])
    {
        j=i;
        for(k=0;k<strlen(sstr);k++,j++)
        {
            tstr[k]=lstr[j];
        }
    }
    if(strcmp(tstr,sstr)==0)
        c++;
 }
 cout<<c;
 return 0;
}

Upvotes: 1

Views: 571

Answers (3)

Ali Akber
Ali Akber

Reputation: 3800

This will solve your problem more efficiently in O(n*m) complexity, where n is large string size and m is small string size.

#include<iostream>
#include<cstring>
using namespace std;
int main()
{
  int i, j, k, c=0;
  char lstr[30],sstr[10];
  cout<<"Enter large string:"<<endl;
  cin>>lstr;
  cout<<"Enter small string:"<<endl;
  cin>>sstr;
  for(i=0; lstr[i]; i++) // You don't need to calculate strlen each time. This loop will break when lstr reaches null ('\0') character
  {
    if(lstr[i]==sstr[0])
    {
        for(k=0,j=i; sstr[k] && lstr[j]; k++,j++) // don't need to calculate strlen each time
        {
            if(sstr[k]!=lstr[j])  // Break if not match
                break;
        }
        if(k==strlen(sstr)) // Whole string matched
            c++;
    }
  }
  cout<<c<<"\n";
  return 0;
}

If you want to solve this problem in O(n) complexity you can use KMP algorithm. Which is the best choice for this kind of problems.

Upvotes: 1

justmscs
justmscs

Reputation: 756

This should work, add a '\0' to terminate c-style string, and move if(strcmp(tstr,sstr)==0) in the if(lstr[i]==sstr[0]) statement(otherwise you will continuing increment c when lstr[i] != sstr[0]):

#include<iostream>
#include<cstring>
using namespace std;
int main()
{
  int i, j, k, c=0;
  char lstr[30],sstr[10],tstr[10];
  cout<<"Enter large string:"<<endl;
  cin>>lstr;
  cout<<"Enter small string:"<<endl;
  cin>>sstr;
  for(i=0;i<strlen(lstr);i++)
  {
    if(lstr[i]==sstr[0])
    {
        j=i;
        for(k=0;k<strlen(sstr) && j<strlen(lstr);k++,j++)
        {
            tstr[k]=lstr[j];
        }
        tstr[k] = 0;
    //  ^^^^^^^^^^^^
        if(strcmp(tstr,sstr)==0)
            c++;
    }
  }
  cout<<c;
  return 0;
}

Upvotes: 2

John Zwinck
John Zwinck

Reputation: 249123

It's much easier if you use C++ strings instead of C ones:

  int c=0;
  string lstr, sstr;
  cout<<"Enter large string:"<<endl;
  cin>>lstr;
  cout<<"Enter small string:"<<endl;
  cin>>sstr;

  for (size_t pos = 0;
       (pos = lstr.find(sstr, pos)) != string::npos;
       pos++)
  {
    c++;
  }

  cout<<c;

Upvotes: 3

Related Questions