生成字典序大于输入的字符串

Question

给定一个输入字符串 A，是否有一种简洁的方法可以生成一个按字典顺序大于 A 的字符串 B，即 A < B == true？

我的原始解决方案是：

B = A;
++B.back();

但一般来说这是行不通的，因为：

A 可能为空
A 的最后一个字符可能接近回绕，在这种情况下，生成的字符将具有较小的值，即 B < A.
每次都添加一个额外的字符是一种浪费，并且会很快形成不合理的大字符串。

所以我想知道是否有一个标准库函数可以帮助我，或者是否有一个策略可以很好地扩展当我想从任意字符串开始时。

Answer 1

您可以将A复制到B中，然后查看最后的字符。如果最后一个字符不是您范围内的最后一个字符，那么您只需将它加一即可。

不然你可以看看last-1,last-2,last-3。如果到达字符列表的前面，则追加到长度。

Answer 2

这是我的虚拟解决方案：

std::string make_greater_string(std::string const &input)
{
    std::string ret{std::numeric_limits<
                    std::string::value_type>::min()};
 
    if (!input.empty())
    {
        if (std::numeric_limits<std::string::value_type>::max() 
            == input.back())
        {
            ret = input + ret;
        }   
        else
        {   
            ret = input;
            ++ret.back();
        }   
    }
   
    return ret;
}

理想情况下，我希望避免显式处理所有特殊情况，并使用一些可以更自然地处理它们的工具。已经看过@JosephLarson 的答案，我发现我可以增加比最后一个字符更多的字符，这将改善可实现的范围而无需添加更多字符。

这是根据 post 中的建议进行的改进：

std::string make_greater_string(std::string const &input)
{
    constexpr char minC = ' ', maxC = '~';
    // Working with limits was a pain, 
    // using ASCII typical limit values instead.
    
    std::string ret{minC};
 
    auto rit = input.rbegin(); 
    while (rit != input.rend())
    {
        if (maxC == *rit)
        {
            ++rit;
            if (rit == input.rend())
            {
                ret = input + ret;
                break;
            }
        }
        else
        {
            ret = input;
            ++(*(ret.rbegin() + std::distance(input.rbegin(), rit)));
            break;
        }
    }
   
    return ret;
}

Demo

Answer 3

您可以复制字符串并附加一些字母 - 这将产生字典序更大的结果。

    B = A + "a"

生成字典序大于输入的字符串

Generate string lexicographically larger than input

c++

string

c++-standard-library