0

I've got a problem with a program which finds all substring in a given string. I've tried to make variable "found", which would contain a position of a previously found substring and then start searching from the position. Here's my code:

#include <iostream>
#include <string>
  
using namespace std;
  
int main()
{
    string str;
    string str1;

    cin >> str >> str1;
    int i = 0;
    int found = -1;
    while(found < str1.size()){
        found = str1.find(str, found + 1);
        cout<<str1.find(str, found)<<endl;
        i++;
    }
}

for the following input: "ab aabb" it doesn't print anything. Could you help?

2
  • 5
    The length returned by size() is an unsigned integer. The comparison found < str1.size() will convert found to an unsigned integer, which makes the value -1 very large. So the condition will be false from the beginning and the loop won't even iterate once. Commented Nov 25, 2022 at 13:05
  • A side note: better to avoid using namespace std - see here stackoverflow.com/questions/1452721/….
    – wohlstad
    Commented Nov 25, 2022 at 13:07

3 Answers 3

1

So a little bit of theory first:

substr(a,b) -> returns cut out of the string from position a to position b
find(a) -> returns the position of found character or set of characters 'a'. returns -1 if NOT found.

Let's examine your code:

#include <iostream>
#include <string> //not really needed here. string should already be usable
  
using namespace std; //in small programs is ok but with big programs this could lead to problems with using specific things that could have the same names in std and other library. So its best to avoid this and or any other using namespace you use.
  
int main()
{
    string str; // you should really name your variables better
    string str1;

    cin >> str >> str1; // your variable names are unreadable at first glance
    int i = 0; // iterator cool but why is it needed if you're just using find()
    int found = -1; // good variable although the name "pos" would probably be better as to further explain to the programmer what the variable does
    while(found < str1.size()){ //not really sure what you were going for here
        found = str1.find(str, found + 1); // this could have been your while logic above instead
        cout<<str1.find(str, found)<<endl; // this finds the exact same position again using more resources. your variable found stores the position so doing cout << found << here would be better
        i++; 
    }
}

Now let's see why your code doesn't show anything on console:

#include <iostream>
#include <string>
  
using namespace std;
  
int main()
{
    string str;
    string str1;

    cin >> str >> str1; //you input ab as str and abbb as str1
    int i = 0;
    int found = -1;
    while(found < str1.size()){ //first iteration is while(-1 < 4)
        found = str1.find(str, found + 1); //<-- find needs just 1 parameter. heres your problem
        cout<<str1.find(str, found)<<endl;
        i++;
    }
}

str1.find("ab); -> function find searches for "ab" in string str1. You don't need to add where it's meant to search for. Also the fact that your while loop is dependant on found < str1.size() and not anything to do with your iterator means your loop will go on forever. whenever this happens most IDE's crash your program giving you nothing cout'ed.

Fix:

#include <iostream>

using namespace std;

int main()
{
    string str;
    string str1;
    int pos;
    cin >> str >> str1;
    for(int i = 0; i < str1.size(); i++) // this or could be while(true)
    {
        pos = str1.substr(i).find(str); //finds your string in the rest of the line
        if (pos == -1)
        {
            //NOT FOUND
            break; //stops
        }
        else
        {
            //FOUND
            cout << pos + i << endl; //pos is position in the cut out after adding i we get global position
            i += pos; // skip characters after we found them to NOT be found again
        }
    }
}

0
1

Another possible solution would be:

  • Walk the input string until the point you know the substring cannot fit anymore.
  • For each input string position, check if each substring starts with the substring (starts_with only since C++20).

[Demo]

#include <iostream>
#include <string>

int main() {
    std::string str{ "ab aab" };
    std::string sub{ "ab" };
    int count{};
    size_t last_index{ str.size() > sub.size() ? str.size() - sub.size() : 0 };
    for (size_t i{0}; i <= last_index; ++i) {
        if (str.substr(i).starts_with(sub)) {
            count++;
        }
    }
    std::cout << count;
}

// Outputs: 2
0
int find_substr(string substr, string str) {

  int postion = 0;
  auto beginning = str.c_str();
  int i = 0;
  char* p = (char *)beginning;
  while (p && '\0'!=p)
  {
  p = strstr(p, substr.c_str());
  if (!p)
    break;
  cout << "A substring is at index:" << p - beginning << "\n";
  p++;
  };
  return 0;
}


void test()
{
  string substr, str;
  {
    substr = "ab"; str = "aabb";
    cout << "Finding " << substr << " in " << str << "\n";
    find_substr(substr, str);
    cout << "\n";
  }
  {
    substr = "ab"; str = "abab";
    find_substr(substr, str);
    cout << "\n";
  }
  {
    substr = "a"; str = "11111111111111111111111a";
    find_substr(substr, str);
    cout << "\n";
  }
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.