c++ - 除了使用 str.substr( ) 在给定位置提取子字符串之外，还有其他方法吗？

Question

我正在尝试比较两个 std::strings，并确定字符串 A 是否与字符串 B 相同，但插入或删除了单个字符。 否则返回假。 例如:“start”和“strt”或“ad”和“add” 目前:

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