Kā kustēties? Nu ļoti vienkārši - uzturi skaitītāju, kuru pārbīdi.

size_t count_ending_newlines(const std::string& str)
{
    const std::string newline = "
";
    const size_t newline_size = newline.size();

    size_t pos = str.size();
    while (pos >= newline_size)
    {
        if (str.substr(pos - newline_size, newline_size) != newline)
        {
            break;
        }
        pos -= newline_size;
    }

    return (str.size() - pos) / newline_size;
}