Где ломается std::regex
Регулярные выражения в C++ находятся в заголовке <regex>, и шаблоны пишутся почти так же, как в Python. Поэтому решение задания 24 легко перенести как есть. Например, для самой длинной цепочки без букв G, W и P — шаблон [^GWP]+ и максимум длины совпадений.
<algorithm>
<iostream>
<regex>
<string>
using namespace std;
int main() {
string s;
getline(cin, s);
// Тот же шаблон, что на Python: разрешённые буквы подряд.
// На примере из условия работает, на файле в миллион символов падает.
regex allowed("[^GWP]+");
long long best = 0;
for (sregex_iterator it(s.begin(), s.end(), allowed), end; it != end; ++it)
best = max(best, (long long)it->length());
cout << best << endl;
}
На примере из условия программа выводит верный ответ. Проблема — в стандартной библиотеке libstdc++, с которой работает g++. В GCC 15 и более старых версиях std::regex проверяет каждый следующий символ совпадения вложенным вызовом функции, и расход стека растёт с длиной совпадения. Что получится, зависит от того, где запущена программа. Вот что показала наша проверка на строке из одних разрешённых букв:
- Windows, g++ 15.2 (так же устроен MinGW в Code::Blocks). Стек небольшой: программа работала на совпадении в 1000 символов и падала на 10 000 с кодом 0xC00000FD (−1073741571) — переполнение стека. Ответа нет.
- Linux, g++ 15.3, обычный стек 8 МБ. 10 000 символов — работает, 100 000 — Segmentation fault. Из 16 тестов задачи 24-01 не проходят три больших.
- Проверка на этом сайте. Программа не падает, но на длинной цепочке превышает лимит памяти: вердикт «Превышение памяти».
- Linux, g++ 16.2. Здесь
std::regexпереписан и не зависит от размера стека. Программа тратит около 90 байт на символ: 1 200 000 символов — около 100 МБ и 0,2 с. Все 16 тестов задачи 24-01 проходят.
Значит, прямой перевод с Python надёжно работает только в GCC 16, а какой компилятор будет на экзамене, заранее не известно. Всё это происходит только при длинном совпадении — когда шаблон описывает всю цепочку: [^GWP]+, [A-Z]+, (?:[QRW][124])+. Короткие совпадения вроде (?=ABABA) безопасны. Но в задании 24 строка длиной около миллиона символов, и длинная цепочка может оказаться в любом файле.
Решайте циклом
В C++ задание 24 надёжнее решать обычным проходом по строке. Он не зависит от версии компилятора, не тратит память сверх самой строки и работает быстрее регулярного выражения. Для цепочки без G, W и P достаточно двух чисел: current — длина цепочки разрешённых символов, которая заканчивается на текущем символе, и best — рекорд.
<algorithm>
<iostream>
<string>
using namespace std;
int main() {
string s;
getline(cin, s);
if (!s.empty() && s.back() == '\r')
s.pop_back();
// current — длина цепочки разрешённых символов, которая заканчивается здесь.
int current = 0, best = 0;
for (char ch : s) {
if (ch == 'G' || ch == 'W' || ch == 'P')
current = 0;
else
current += 1;
best = max(best, current);
}
cout << best << endl;
}
Запрещённая буква обнуляет current, разрешённая увеличивает его на один. Рекорд обновляется после каждого символа, поэтому цепочка в конце строки тоже попадает в ответ. В нашей проверке строка в 1 200 000 символов обработана примерно за десятую долю секунды вместе с запуском программы.
Так же, одним проходом, решаются чередование букв и цифр и вхождения с пересечениями. Для окна с ограничением числа букв нужны две границы — это скользящее окно. Код на C++ для каждой задачи есть в статье о её приёме.
Типичные ошибки в цикле
- Рекорд только при сбросе. Если обновлять
bestтолько перед обнулениемcurrent, цепочка в конце строки не попадёт в ответ. Сравнивайте после каждого символа или ещё раз после цикла. - Символ \r в конце строки. Если файл записан в Windows, а читается в другой системе,
getlineоставит в конце строки\r. Программа посчитает его разрешённым символом, и ответ может вырасти на единицу. Уберите его, как в коде выше. - Неполное сравнение. Запрещённую букву проверяют тремя сравнениями через
||:ch == 'G' || ch == 'W' || ch == 'P'. Разрешённая — это три неравенства через&&. Записьch == 'G' || 'W'всегда истинна:'W'сам по себе не ноль.