Есть ли альтернатива использованию str.substr() для извлечения подстроки в данной позиции?

Question

Я пытаюсь сравнить две std :: strings и решить, является ли строка A такой же, как строка B, но с вставкой или удалением одного символа. В противном случае он возвращает false. Например: «старт» и «STRT» или «объявление» и «добавить» В настоящее время:

if(((sizeA - sizeB) != 1) 
    && ((sizeB - sizeA) != 1)) 
{ 
    return false; 
} 

if(sizeA < sizeB) 
{ 
    for(int i = 0; i < sizeA; ++i) 
    { 
     if(stringA[i] != stringB[i]) 
     { 
      if(stringA.substr(i) 
       == stringB.substr(i + 1)) 
      { 
       return true; 
      } 
      else return false; 
     } 
    } 
} //with another loop that runs only if stringA is larger than stringB 

Это работает безупречно, но дргиЙ говорит мне, что эта функция в настоящее время увязла. Я попытался преобразовать цикл for, чтобы использовать итераторы для доступа к символам, но это удвоило мое время выполнения. Ive сузил его до использования std :: string.substr(), потому что он строит новые строки каждый раз, когда stringA и stringB различаются по размеру на 1.

Когда первый символ отличается, мне нужен более эффективный способ чтобы проверить, должен ли я удалить этот символ, будут ли две строки равны?

Answer 1

Try:

if (stringA.compare(i, stringA.npos, stringB, i+1, stringB.npos) == 0) { 
    /* the strings are equal */ 
} 

В this write-up, это версия (3) из std::basic_string::compare.

Answer 2

Кажется, как только будет известно, есть ли разница в одном значении, сравнение может быть более эффективным с помощью одного прохода над строкой: найти местоположение разницы, пропустить символ и посмотреть, есть ли хвост тоже самое. Для этого, очевидно, необходимо знать, какой из них меньше строк, но это тривиально, чтобы определить:

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; 
    } 
} 

Answer 3

Если ваш компилятор поддерживает это может быть стоит проверить новый ISO/IEC TS 19568:xxxx Техническая спецификация string_view класса.

Он обеспечивает неизменный вид строки через ссылку без копирования строку самих так обещает быть гораздо более эффективными при работе с подстроками.

#include <experimental/string_view> 

using std::experimental::string_view; 

bool func(string_view svA, string_view svB) 
{ 
    // ... stuff 

    if(svA.size() < svB.size()) 
    { 
     for(int i = 0; i < svA.size(); ++i) 
     { 
      if(svA[i] != svB[i]) 
      { 
       if(svA.substr(i) 
        == svB.substr(i + 1)) 
       { 
        return true; 
       } 
       else return false; 
      } 
     } 
    } 

    // ... stuff 
    return false; 
} 

Как вы можете видеть, что это работает довольно много, как дроп-ин для замены std::string (или const char* и т.д ...). Просто передайте свои обычные std::string объекты в качестве аргументов функции, а параметры string_view будут инициализированы из переданных в строк.