i trying compare 2 std::strings, , decide if string same string b, insertion or deletion of single character. otherwise returns false. example: "start" , "strt" or "ad" , "add" currently:
if(((sizea - sizeb) != 1) && ((sizeb - sizea) != 1)) { return false; } if(sizea < sizeb) { for(int = 0; < sizea; ++i) { if(stringa[i] != stringb[i]) { if(stringa.substr(i) == stringb.substr(i + 1)) { return true; } else return false; } } } //with loop runs if stringa larger stringb
this works flawlessly, gprof tells me function being bogged down. tried converting loop use iterators access chars, doubled run time. ive narrowed down use of std::string.substr( ) because constructing new strings each time stringa , stringb differ in size 1.
when first character differs, need more efficient way check if delete character, 2 strings equal?
it seems, once known whether there 1 character difference comparison can done more effective single pass on string: find location of difference, skip character, , see if tail same. end necessary know 1 smaller string that's trivial determine:
bool onechardiff(std::string const& shorter, std::string const& longer) { if (shorter.size() + 1u != longer.size() { return false; } typedef std::string::const_iterator const_iterator; std::pair<const_iterator, const_iterator> p = std::mismatch(shorter.begin(), shorter.end(), longer.begin()); return std::equal(p.first, shorter.end(), p.second + 1); } bool atmostonechardiff(std::string const& s0, std::string const& s1) { if (s0.size() < s1.size()) { return onechardiff(s0, s1); else if (s1.size() < s0.size()) { return onechardiff(s1, s0); } else { return s0 == s1; } }
Comments
Post a Comment