有没有使用 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

这完美无缺，但 gprof 告诉我这个功能正在陷入困境。我尝试将 for 循环转换为使用迭代器访问字符，但这使我的运行时间翻了一番。我将其缩小到我对 std：：string.substr（） 的使用，因为它每次 stringA 和 stringB 的大小相差 1 时都会构造新的字符串。

当第一个字符不同时，我需要一种更有效的方法来检查我是否要删除该字符，那么两个字符串是否相等？

Answer 1

似乎，一旦知道是否存在一个字符差异，就可以通过单次传递字符串来更有效地进行比较：找到差异的位置，跳过字符，看看尾巴是否相同。为此，显然有必要知道哪一个是较小的字符串，但确定这一点是微不足道的：

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 2

尝试：

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

在这篇文章中，这是std::basic_string::compare的版本（3）。

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参数将从传入的字符串初始化。