Searching backwards in a string

This is a discussion on Searching backwards in a string within the C++ Programming forums, part of the General Programming Boards category; Which algorithm or string::find should we use to search backwards in a string? Thank you!...

  1. #1
    Registered User
    Join Date
    Dec 2007
    Posts
    812

    Searching backwards in a string

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

    Thank you!
    Compiler MSVC++ 2013 with Code::Blocks.

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    I think the string method is called rfind (to find the last occurrence of something if that's what you mean).
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  3. #3
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    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".
    Last edited by CornedBee; 03-07-2008 at 10:14 AM.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  4. #4
    Registered User
    Join Date
    Dec 2007
    Posts
    812
    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;
    }
    Last edited by Ducky; 03-08-2008 at 02:39 AM.
    Compiler MSVC++ 2013 with Code::Blocks.

  5. #5
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  6. #6
    Registered User
    Join Date
    Dec 2007
    Posts
    812
    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.
    Compiler MSVC++ 2013 with Code::Blocks.

  7. #7
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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;
    }
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  8. #8
    Registered User
    Join Date
    Dec 2007
    Posts
    812
    Great, i get it now, thank you!
    Compiler MSVC++ 2013 with Code::Blocks.

  9. #9
    Registered User
    Join Date
    Dec 2007
    Posts
    812
    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".
    Last edited by Ducky; 03-08-2008 at 01:28 PM.
    Compiler MSVC++ 2013 with Code::Blocks.

  10. #10
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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?
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  11. #11
    Registered User
    Join Date
    Dec 2007
    Posts
    812
    Well at least not for me...
    I gotta think about it.
    Compiler MSVC++ 2013 with Code::Blocks.

  12. #12
    Registered User
    Join Date
    Dec 2007
    Posts
    812
    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;
    }
    Last edited by Ducky; 03-09-2008 at 01:57 AM. Reason: Solved
    Compiler MSVC++ 2013 with Code::Blocks.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. String Class
    By BKurosawa in forum C++ Programming
    Replies: 117
    Last Post: 08-09-2007, 02:02 AM
  2. Compile Error that i dont understand
    By bobthebullet990 in forum C++ Programming
    Replies: 5
    Last Post: 05-05-2006, 10:19 AM
  3. Visual C++ 2005 linking and file sizes
    By Rune Hunter in forum C++ Programming
    Replies: 2
    Last Post: 11-12-2005, 10:41 PM
  4. Warnings, warnings, warnings?
    By spentdome in forum C Programming
    Replies: 25
    Last Post: 05-27-2002, 07:49 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21