What is time complexity of string::rfind method in c++?From what I understood, rfind is reversing the string and then doing string::find. Am I correct? Then it should be O(n)
Best Answer
No, you are not correct. rfind searches from the back of the string without reversing the string. The complexity is the same as for a forward find.
I haven't found anything in the standard requiring this, but any search algorithm that you can use for find (like a naive search or a Boyer-Moore / Boyer-Moore-Horspool search) can also be used for rfind - so I find it highly unlikely that any library implementors would choose a less effective algorithm for their rfind implementation.