Searching backwards in a string

Which algorithm or string::find should we use to search backwards in a string?

Thank you!

I think the string method is called rfind (to find the last occurrence of something if that's what you mean).

Or std::find with string's reverse iterators.

But be careful: the behaviour of the two is not the same. rfind simply searches for the substring, but starting from the back. find with reverse iterators actually treats the string as if it was reversed and searches for the substring this way.

That is, given "snafoobar", rfind finds the substring "foo" at position 3, find doesn't find it at all. But find would find the substring "abo".

Thank you Anon and Cornedbee!
Im sorry i didnt express myself well enough.

Lets say i already found an occurence in a string and now i wanna find something else from that point, backwards.
I think maybe i could use for this the search() algorithm.

Here would be the program if somebody would mind to take a look at it.

Code:

---

int main ()
{
  vector<string> myvector;
  string::iterator it;
 
  string str = "The lion sleeps tonight";
  string str2 = "lion";
  string str3 = "sleeps";
  myvector.push_back(str);
 
  string::size_type pos = 0;
  if (( pos = str.find(str3, pos)) != string::npos)
  {
    cout<<"str3 pos = "<< pos <<endl;
  }

  it = search (myvector[0].pos, myvector[0].begin(), str2.begin(), str2.end());
  if (it != myvector[0].end())
  {
    cout << "Match found at position: " << distance(myvector[0].begin(),it)+1 << endl;
  }
  else
    cout << "Match not found." << endl;
 
  system("pause");
  return 0;
}

---

Both find and rfind have another parameter, a size_t that tells from which position the search should start from. See the reference. In case of rfind this means that rfind will look for the last occurrence of something up to the index that you specify.

As to the attempt at search: you can't pass arbitrary types and arbitrary iterators to std algorithms and hope it works.

And again, where do you get this strange notion that you need a vector with a single string in it, to pass the string to std::algorithms? You know, instead of vector[0] you could use str in the first place! The presence of a single-item vector does not change the fact that you are (or should be) working with string::iterators.

I'm not sure though, whether there is a std algorithm that can find the last occurrence of a substring in a string.

Thanks Anon for the explication, thats exactly what i was looking for.

"And again, where do you get this strange notion that you need a vector with a single string in it"
I dont, im just going to use a vector with a lots of element in my final program.

I changed the program, i use rfind instead of search.
I can make it work with this version:
size_type rfind( const char* str, size_type index );
But it wont compile with this:
size_type rfind( const char* str, size_type index, size_type num );
Im using the size_type num parameter to search only 5 character long.
I cant see what im doing wrong.

Code:

---

int main () {
  vector<string> myvector;
  string::iterator it;
 
  string str = "The lion aaaaaaa sleeps tonight";
  string str2 = "lion";
  string str3 = "sleeps";
  myvector.push_back(str);
  int loc = 0;
 
  string::size_type pos = 0;
  if (( pos = str.find(str3, pos)) != string::npos)
  {
    cout<<"str3 pos = "<< pos <<endl;
  }
  loc = myvector[0].rfind ( str2, pos, 5);

  if (loc != string::npos)
  {
    cout << "Match found at position: " << loc << endl;
  }
  else
    cout << "Match not found." << endl;
 
  system("pause");
  return 0;
}

---

The aaaaaaa is there on purpose for not to find the string.

You are not really using this version: size_type rfind( const char* str, size_type index, size_type num ).

The first argument, str2, is not a const char*. It is a string. You can obtain a const char* from a string using the c_str member.

And please, unless you are going to perform this search operation on a collection of strings, stop this non-sense with a vector containing only one item.

(And please provide a compilable example, together with includes.)

Code:

---

#include <string>
#include <iostream>
using namespace std;

int main () {
  string str = "The lion aaaaaaa sleeps tonight";
  string str2 = "lion";
  string str3 = "sleeps";
  string::size_type loc = 0; //use correct type
  string::size_type pos = 0;

  if (( pos = str.find(str3, pos)) != string::npos)
  {
    cout<<"str3 pos = "<< pos <<endl;
  }
  loc = str.rfind ( str2.c_str(), pos, 5);

  if (loc != string::npos)
  {
    cout << "Match found at position: " << loc << endl;
  }
  else
    cout << "Match not found." << endl;

  system("pause");
  return 0;
}

---

Great, i get it now, thank you!

Hmmm interesting...

If you put a number smaller than 5 in the place of 5 (size_type num) it will find it and say that its at position 4.
And if you put a much bigger it wont find it at all.

It means that it start to search from the beginning of the string, that is to say from "The".

I thought it will start from "sleeps", as "sleeps" is "pos".

I have never used this version myself, and the third argument probably doesn't mean what we expected. What it actually means is how many characters from the search string are to be used. 5 is longer than the string, therefore it is not found ("lion" is not followed by the \0 character). If the third argument is less, only that many characters are used from the string "lion".

It seems that with std::string find methods, the search will always run up to the end (or beginning) of the string.

But if you want to check whether "sleeps" is preceeded by "lion ", wouldn't that be quite easy to do?

Well at least not for me... :)
I gotta think about it.

Ok i think i found it

Code:

---

#include <string>
#include <iostream>
using namespace std;

int main () {
  string str = "The lion sleeps tonight";
  string str2 = "lion";
  string str3 = "sleeps";
  string::size_type loc = 0;
  string::size_type pos = 0;

  if (( pos = str.find(str3, pos)) != string::npos)
  {
    cout<<"str3 pos = "<< pos <<endl;
  }
  loc = str.rfind ( str2,pos);
  if (loc != string::npos)
  {
    if ( loc < (pos - (str2.size()+ 1))) // loc <(17 - (4+1))
        cout << "Match not found." << endl;
    else
        cout << "Match found at position: " << loc << endl;
  }
  else
      cout << "Match not found." << endl;
  system("pause");
  return 0;
}

---