Обработка текста - Язык программирования C++ для спортивного программирования
Неделя 5Строки и Символы, Обработка текста, Обработка ввода
Обработка текста
Один проход по тексту: сумма цифр и подсчёт по видам, проверка правил с флагами, изменение каждого символа на месте через char &, сдвиг букв по кругу алфавита через % 26, оба конца (разворот, палиндромы), серии одинаковых символов и их сжатие, подсчёт каждой буквы в векторе из 26.
Теория
Урок 5 из 10
18 мин чтения
Вопросов: 5
Большинство задач на текст решаются одинаково: пройдите по строке один раз и
сделайте что-то с каждым символом — посчитайте его, проверьте, измените или
сравните с соседом. Это приёмы обхода с недели 4, только с символами вместо
чисел, плюс несколько, которые нужны только тексту. Этот урок разбирает их по
одному.
Проход по строке
Обойти все символы можно двумя циклами. С индексом — когда важна позиция:
Или с for по элементам с недели 4 — когда важны только сами символы:
Подсчёт — это счётчик внутри if. Здесь он считает гласные в слове:
Проходим по слову: считаем гласные
C++
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 ios_base::sync_with_stdio(false);
6 cin.tie(NULL);
7
8 string s;
9 cin >> s;
10 int n = s.size(), cnt = 0;
11 for (int i = 0; i < n; i++) {
12 char c = s[i];
13 if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
14 cnt++;
15 }
16 }
17 cout << cnt << "\n";
18 return 0;
19}
Читаем слово
строка 9
cin >> s читает одно слово: piano. Его 5 символов лежат в s[0] … s[4].
s5 ячеек
'p'
'i'
'a'
'n'
'o'
0
1
2
3
4
ввод
piano
n—cnt—i—c—
нажми пуск
1 / 28
дальше
Практика: Подсчёт и Изменение символов
Подсчитайте символы по видам, проверьте правила с флагами и измените каждую букву текста.
Тот же цикл умеет складывать. Строка из цифр — это число, которое не поместится
ни в один тип, а его сумма цифр — просто sum += c - '0'; для каждого символа, потому что
c - '0' — значение цифры.
Подсчёт по видам
Чтобы отнести каждый символ к одному из нескольких видов, используйте цепочку
if / else if — тогда каждый символ посчитается ровно один раз:
Проверьте результат: три счётчика в сумме должны дать s.size(). Если строка
прочитана через getline, сначала уберите \r в конце (см. прошлый урок) — иначе
на каждом тесте, сделанном в Windows, он посчитается как «остальной» символ.
Проверка правил с флагами
Правило про весь текст проверяют флагами — переменными bool, которые
меняются во время прохода. Флаги бывают двух видов, и начинаются они
противоположно:
«Есть ли хотя бы один …?» начинается с false и становится true, когда
такой найден.
«Каждый ли символ …?» начинается с true и становится false на первом
символе, который нарушает правило.
После цикла флаги объединяют через && и || вместе с правилами о длине.
Сайт принимает имя пользователя, если в нём не больше 12 символов, оно
начинается с буквы, состоит только из строчных букв и цифр и содержит хотя бы
одну цифру. Выведите OK или Try another.
Ввод
Вывод
isalpha(s[0]) проверяет первый символ без цикла. Вся проверка — один проход,
сколько бы ни было правил.
Изменение каждого символа
Чтобы менять саму строку, for по элементам нужен с &: for (char &c : s)
делает cвторым именем ячейки, а не копией, поэтому изменение c меняет
s. Без & цикл менял бы копию, и s осталась бы прежней.
char &c: меняем каждую букву на месте
C++
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 ios_base::sync_with_stdio(false);
6 cin.tie(NULL);
7
8 string s;
9 getline(cin, s);
10 for (char &c : s) {
11 if (c >= 'a' && c <= 'z') {
12 c = c - 32;
13 }
14 }
15 cout << s << "\n";
16 return 0;
17}
Читаем целую строку
строка 9
getline читает Hi, Bob! вместе с пробелом и знаками: 8 символов.
s8 ячеек
'H'
'i'
','
' '
'B'
'o'
'b'
'!'
0
1
2
3
4
5
6
7
ввод
Hi, Bob!
нажми пуск
1 / 22
Цикл с индексом делает то же через s[i] = …, и именно его выбирают, когда
изменение зависит от позиции — например, заглавные на чётных индексах и
строчные на нечётных:
s[i] = toupper(s[i]); записывает код в char, и он снова становится
символом — char(…) здесь не нужен.
Чтобы убрать или добавить символы, собирайте новую строку, а не меняйте
старую: начните с string t = ""; и делайте t += c; для каждого символа,
который нужно оставить.
Сдвиг букв по кругу алфавита
Сдвинуть букву на k мест вперёд — и после z вернуться к a — это снова
круглый стол с недели 4: возьмите позицию буквы, прибавьте k и возьмите % 26:
Для 'y' и k = 3: позиция 24, 24 + 3 = 27, 27 % 26 = 1, а на позиции 1 стоит
'b'. Заглавные делают то же с 'A'; всё, что не буква, остаётся как есть.
Почему не просто c + k? После 'z' это уже не буква, а char вмещает коды
только до 127 — 'z' + 25 туда даже не помещается. Работайте с позицией, то
есть с int, и превращайте её в букву в самом конце.
Сдвиг назад на k мест требует аккуратности: (c - 'a' - k) % 26 может
быть отрицательным, потому что в C++ остаток % от отрицательного числа отрицателен
(-3 % 26 равно −3). Прибавьте 26 перед % — а если k может быть больше 26,
сначала уменьшите его: k %= 26.
Секретную записку написали, сдвинув каждую букву на k мест вперёд. Прочитайте
записку (строку с пробелами) и k и выведите исходное сообщение.
Ввод
Вывод
Теперь покрутите шифровальное кольцо сами: каждый раунд пропускает один символ
через ту же формулу.
Шифровальное кольцо шпионапопробуй!
Оба конца
Приёмы с двумя концами с недели 4 работают со строками без изменений. Чтобы
напечатать слово задом наперёд, пройдите индексы от n - 1 до 0. Слово —
палиндром, если каждый символ равен своему зеркальному:
а swap(s[i], s[j]), где i и j идут навстречу друг другу, разворачивает
строку на месте. Сравнение идёт по кодам, поэтому 'A' и 'a' — разные
символы: Level не палиндром, пока его не сделать целиком строчным через
tolower.
Серии
Серия — это участок одинаковых символов подряд, например bbb в aabbbc.
Самая длинная серия — это серия чисел с недели 4, со сравнением s[i] и
s[i - 1]:
Чтобы записать каждую серию как её букву и длину — это сжатие серий (run-length
encoding), — нужно знать, где серия заканчивается: на последнем индексе или
там, где следующий символ другой:
Серии: записываем aaabcc как a3b1c2
C++
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 ios_base::sync_with_stdio(false);
6 cin.tie(NULL);
7
8 string s;
9 cin >> s;
10 int n = s.size(), run = 0;
11 string out = "";
12 for (int i = 0; i < n; i++) {
13 run++;
14 if (i == n - 1 || s[i] != s[i + 1]) { // the run ends at i
15 out += s[i];
16 out += to_string(run);
17 run = 0;
18 }
19 }
20 cout << out << "\n";
21 return 0;
22}
Читаем слово
строка 9
aaabcc: серии из a, b и c.
s6 ячеек
'a'
'a'
'a'
'b'
'c'
'c'
0
1
2
3
4
5
ввод
aaabcc
n—run—out—i—
нажми пуск
1 / 39
i == n - 1 || стоит первым нарочно. Когда это истинно, || не смотрит дальше,
поэтому s[i + 1] никогда не читается за концом строки.
Подсчёт каждой буквы
«Сколько раз встречается каждая буква?» требует 26 счётчиков — вектор из 26
ячеек, по одной на букву. c - 'a' превращает строчную букву в её индекс, от 0
до 25:
После этого cnt[i] — сколько раз встретилась буква char('a' + i). Один проход
по 26 счётчикам находит самую частую букву (с > при ничьей побеждает та, что
раньше в алфавите), буквы, которых нет совсем, или число разных букв. Два слова
состоят из одних и тех же букв ровно тогда, когда их 26 счётчиков совпадают.
Проверяя клавиатуру, набирают предложение, в котором должна быть каждая буква.
Прочитайте предложение и выведите буквы, которые ни разу не встретились, в
алфавитном порядке, — или every key works.
Ввод
Вывод
tolower(c) - 'a' считает T и t в одной ячейке. Подсчёт — один проход по
предложению, а ответ — один проход по 26 ячейкам.
Проверьте себя
А вы знали?
Так отправляет страницу факс. Отсканированная строка — это в основном длинные
серии белых точек и немного чёрных, поэтому вместо каждой точки аппарат
отправляет длины серий — «1500 белых, 12 чёрных, 300 белых…» — и страница,
которая точка за точкой шла бы минуты, проходит за секунды.
int n = s.size();for(int i = 0; i < n; i++){ // s[i] — символ с индексом i}
for(char c : s){ // c — по очереди каждый символ}
проверь себя1 балл
Флаг «каждый символ пароля — цифра» должен начинаться с false и становиться true, когда найдена цифра.
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Что напечатает cout << (2 - 5) % 26;?
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Программа считает буквы слова banana с помощью vector<int> cnt(26, 0); и cnt[c - 'a']++;. Чему потом равно cnt[13]?
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Что напечатает этот код?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Чему равно char('a' + ('x' - 'a' + 5) % 26)?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
aziz2010
OK
Phhw ph diwhu vfkrro, Dclc!
3
Meet me after school, Aziz!
The quick brown fox jumps over the lazy cat
dg
int letters = 0, digits = 0, others = 0;for(char c : s){ if(isalpha(c)){ letters++;} else if(isdigit(c)){ digits++;} else{ others++; // пробелы, знаки, всё остальное}}
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); string s; cin >> s; bool allOk = true; // все символы допустимы? пока не встретится недопустимый bool hasDigit = false; // есть ли цифра? пока не найдена for(char c : s){ if(!(islower(c) || isdigit(c))){ allOk = false;} if(isdigit(c)){ hasDigit = true;}} int n = s.size(); if(allOk && hasDigit && isalpha(s[0]) && n <= 12){ cout << "OK\n";} else{ cout << "Try another\n";} return 0;}
for(int i = 0; i < n; i++){ if(i % 2 == 0){ s[i] = toupper(s[i]);} else{ s[i] = tolower(s[i]);}}
c = char('a' +(c - 'a' + k) % 26); // строчная буква, на k мест дальше
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); string s; getline(cin, s); // в записке есть пробелы int k; cin >> k; k %= 26; // полный оборот на 26 ничего не меняет for(char &c : s){ // &: меняем саму записку if(c >= 'a' && c <= 'z'){ c = char('a' +(c - 'a' - k + 26) % 26); // на k назад, по кругу алфавита} else if(c >= 'A' && c <= 'Z'){ c = char('A' +(c - 'A' - k + 26) % 26);}} cout << s << "\n"; return 0;}
bool pal = true;for(int i = 0; i < n / 2; i++){ if(s[i] != s[n - 1 - i]){ pal = false;}}
int run = 1, best = 1;for(int i = 1; i < n; i++){ if(s[i] == s[i - 1]){ run++;} else{ run = 1;} best = max(best, run);}