Обновление 2019-06-24: После ночного сна проблема кажется намного проще, чем моя первая попытка выглядела так. Я оставил предыдущий ответ ниже по историческим причинам.
Кодировка UTF-8 , самосинхронизирующаяся . Это позволяет определить, является ли произвольно выбранная единица кода в потоке символов началом последовательности кодов. Последовательность UTF-8 может быть разбита слева от начала кодовой последовательности.
Начало кодовой последовательности является либо символом ASCII (0xxxxxxxb), либо старшим байтом (11xxxxxxb) в многобайтовой последовательности. Конечные байты следуют шаблону 10xxxxxxb. Начало кодировки UTF-8 удовлетворяет условию (code_unit & 0b11000000) != 0b10000000, другими словами: это не завершающий байт.
Самая длинная последовательность UTF-8, не превышающая запрошенное количество байтов, может быть определена в постоянное время (O (1)) с помощью следующего алгоритма:
- Если входное значение не превышает запрошенное количество байтов, возвращает действительное число байтов.
- В противном случае, цикл по направлению к началу (начиная с одной кодовой единицы после запрошенного количества байтов), пока мы не найдем начало последовательности. Верните счетчик байтов влево в начало последовательности.
Введите код:
#include <string_view>
size_t find_max_utf8_length(std::string_view sv, size_t max_byte_count)
{
// 1. Input no longer than max byte count
if (sv.size() <= max_byte_count)
{
return sv.size();
}
// 2. Input longer than max byte count
while ((sv[max_byte_count] & 0b11000000) == 0b10000000)
{
--max_byte_count;
}
return max_byte_count;
}
Это код теста
#include <iostream>
#include <iomanip>
#include <string_view>
#include <string>
int main()
{
using namespace std::literals::string_view_literals;
std::cout << "max size output\n=== ==== ======" << std::endl;
auto test{u8"€«test»"sv};
for (size_t count{0}; count <= test.size(); ++count)
{
auto byte_count{find_max_utf8_length(test, count)};
std::cout << std::setw(3) << std::setfill(' ') << count
<< std::setw(5) << std::setfill(' ') << byte_count
<< " " << std::string(begin(test), byte_count) << std::endl;
}
}
выдает следующий вывод:
max size output
=== ==== ======
0 0
1 0
2 0
3 3 €
4 3 €
5 5 €«
6 6 €«t
7 7 €«te
8 8 €«tes
9 9 €«test
10 9 €«test
11 11 €«test»
Этот алгоритм работает только в кодировке UTF-8. Он не пытается обработать Unicode любым способом. Хотя он всегда будет генерировать действительную последовательность кодирования UTF-8, закодированные кодовые точки могут не образовывать значимой графемы Unicode.
Алгоритм завершается за постоянное время. Независимо от размера ввода, последний цикл будет вращаться не более 3 раз, учитывая текущий предел не более 4 байтов на кодировку UTF-8. Алгоритм будет продолжать работать и завершаться в постоянное время, если кодировка UTF-8 когда-либо будет изменена, чтобы обеспечить до 5 или 6 байтов на кодированную кодовую точку.
Предыдущий ответ
Это можно сделать в O (1), разложив задачу на следующие случаи:
- Ввод не превышает запрошенное количество байтов. Просто верните ввод в этом случае.
- Входное значение длиннее запрошенного числа байтов. Узнайте относительное местоположение в кодировке по индексу
max_byte_count - 1:
- Если это символ ASCII (старший бит не установлен
0xxxxxxxb), мы находимся на естественной границе и можем обрезать строку сразу после нее.
- В противном случае мы находимся либо в начале, в середине, либо в хвосте многобайтовой последовательности. Чтобы узнать где, рассмотрим следующий символ. Если это символ ASCII (
0xxxxxxxb) или начало многобайтовой последовательности (11xxxxxxb), мы находимся в хвосте многобайтовой последовательности, естественной границы.
- В противном случае мы находимся либо в начале, либо в середине многобайтовой последовательности. Итерируйте по направлению к началу строки, пока мы не найдем начало многобайтовой кодировки (
11xxxxxxb). Вырежьте строку перед этим символом.
Следующий код вычисляет длину усеченной строки с учетом максимального количества байтов. Входные данные должны сформировать правильную кодировку UTF-8.
#include <string_view>
size_t find_max_utf8_length(std::string_view sv, size_t max_byte_count)
{
// 1. No longer than max byte count
if (sv.size() <= max_byte_count)
{
return sv.size();
}
// 2. Longer than byte count
auto c0{static_cast<unsigned char>(sv[max_byte_count - 1])};
if ((c0 & 0b10000000) == 0)
{
// 2.1 ASCII
return max_byte_count;
}
auto c1{static_cast<unsigned char>(sv[max_byte_count])};
if (((c1 & 0b10000000) == 0) || ((c1 & 0b11000000) == 0b11000000))
{
// 2.2. At end of multi-byte sequence
return max_byte_count;
}
// 2.3. At start or middle of multi-byte sequence
unsigned char c{};
do
{
--max_byte_count;
c = static_cast<unsigned char>(sv[max_byte_count]);
} while ((c & 0b11000000) != 0b11000000);
return max_byte_count;
}
следующий тестовый код
#include <iostream>
#include <iomanip>
#include <string_view>
#include <string>
int main()
{
using namespace std::literals::string_view_literals;
std::cout << "max size output\n=== ==== ======" << std::endl;
auto test{u8"€«test»"sv};
for (size_t count{0}; count <= test.size(); ++count)
{
auto byte_count{find_max_utf8_length(test, count)};
std::cout << std::setw(3) << std::setfill(' ') << count
<< std::setw(5) << std::setfill(' ') << byte_count
<< " " << std::string(begin(test), byte_count) << std::endl;
}
}
производит этот вывод :
max size output
=== ==== ======
0 0
1 0
2 0
3 3 €
4 3 €
5 5 €«
6 6 €«t
7 7 €«te
8 8 €«tes
9 9 €«test
10 9 €«test
11 11 €«test»