string s1,s2;
cin >> s1 >> s2;
if(s1==s2)
cout << "yes" << endl;
else
cout << "no" << endl;
can someone tell me which algorithm is used in comparison of strings s1==s2 and what is its complexity?
Printable View
string s1,s2;
cin >> s1 >> s2;
if(s1==s2)
cout << "yes" << endl;
else
cout << "no" << endl;
can someone tell me which algorithm is used in comparison of strings s1==s2 and what is its complexity?
Sorry you're not quite going to trick me into answering your homework for you.
I had one of those "this is too easy" moments before I realised that the only reason you would want to know this is for an answer to homework.
Anyway, if you really want to know, the algorithm is implementation defined and its time complexity is O(n^3), where ^ denotes exponentiation.
- Open up your string header.
- Find "operator==".
- Look at what it's doing.
- Determine the complexity.
- Collect underpants
- ...
- Profit
You may have to do some detective work but, for example, the MS Visual Studio 2005 <string> header includes the following for operator==
This calls the "compare" function for basic_string objects (defined in the xstring header). The <xstring> header contains the following relevant sections:Code:template<class _Elem,
class _Traits,
class _Alloc> inline
bool __CLRCALL_OR_CDECL operator==(
const basic_string<_Elem, _Traits, _Alloc>& _Left,
const basic_string<_Elem, _Traits, _Alloc>& _Right)
{ // test for string equality
return (_Left.compare(_Right) == 0);
}
For that last one, you have to do a bit more digging but it basically does something similar to strncmp... and again this is the MS Visual Studio 2005 version of things, your mileage may vary.Code:int __CLR_OR_THIS_CALL compare(const _Myt& _Right) const
{ // compare [0, _Mysize) with _Right
return (compare(0, _Mysize, _Right._Myptr(), _Right.size()));
}
...
int __CLR_OR_THIS_CALL compare(size_type _Off,
size_type _N0, const _Elem *_Ptr, size_type _Count) const
{ // compare [_Off, _Off + _N0) with [_Ptr, _Ptr + _Count)
_DEBUG_POINTER(_Ptr);
if (_Mysize < _Off)
_String_base::_Xran(); // _Off off end
if (_Mysize - _Off < _N0)
_N0 = _Mysize - _Off; // trim _N0 to size
size_type _Ans = _Traits::compare(_Myptr() + _Off, _Ptr,
_N0 < _Count ? _N0 : _Count);
return (_Ans != 0 ? (int)_Ans : _N0 < _Count ? -1
: _N0 == _Count ? 0 : +1);
}