Wolisz obejrzeć?
Olimpijskie Koło Informatyczne nagrywa swoje zajęcia i udostępnia je za darmo. Poniżej 4 odcinki o tym temacie — dobre uzupełnienie, jeśli wolisz obejrzeć niż przeczytać.
Co już umiesz i czego się nauczysz
Ta lekcja zakłada, że przerobiłeś wszystkie poprzednie: Typy zmiennych, Input / Output, If / Else, While loop, For loop, Modulo i Tablice. Z napisami spotkałeś się już wiele razy, tylko zawsze trochę przy okazji. W lekcji o typach poznałeś string, sklejanie plusem, length(), pojedyncze litery s[0] oraz znaki char i ich kody ASCII. W Input / Output — getline. W lekcjach o pętlach przechodziłeś napis znak po znaku i budowałeś nowe napisy, a w tablicach liczyłeś litery w tablicy liczników.
Teraz zbierzemy to wszystko w jednym miejscu i pójdziemy dużo dalej. Zobaczysz, jak napis wygląda od środka i dlaczego s.length() - 1 potrafi dać liczbę z dwudziestu cyfr. Poznasz gotowe funkcje do rozpoznawania znaków i metody, które wycinają, znajdują, usuwają i wstawiają fragmenty tekstu. Dowiesz się, w jakiej kolejności C++ ustawia słowa i dlaczego „Zebra” jest przed „antylopą”. Nauczysz się liczyć na liczbach, które mają sto cyfr, i rozwiązywać zadania olimpijskie z tekstem.
Uczymy się tak samo jak poprzednio. Przepisuj przykłady do swojego edytora i uruchamiaj je. Przy pytaniach „Co wypisze program?” najpierw rozpisz sobie znaki napisu w pudełkach z numerami i odpowiedz w głowie, a dopiero potem sprawdzaj. Po każdej części rób ćwiczenia w sprawdzarce. Części jest osiem, a ćwiczeń dużo — nie spiesz się i rób przerwy.
Napis i wczytywanie
Znaki w pudełkach, długość i pusty napis, a potem słowa, wiersze i cały tekst aż do końca danych.
Znaki i budowanie
Rodzaje znaków i toupper, liczniki i serie, a potem zmienianie i budowanie nowych napisów.
Porównywanie i fragmenty
Kolejność słownikowa, a potem substr, find, erase, insert i replace.
Liczby i olimpiada
Cyfry i olbrzymy zapisane jako napisy, liczniki liter, szyfry, okna i sumy prefiksowe.
Mapa lekcji
Napis to rząd pudełek ze znakami
W lekcji o tablicach poznałeś rząd pudełek z numerami. Napis — zmienna typu string — w środku wygląda bardzo podobnie. To też rząd pudełek, tylko w każdym leży jeden znak, czyli wartość typu char. Pudełka są ponumerowane od zera, a do każdego dobierasz się zapisem s[numer]. Są dwie ważne różnice: napis sam wie, ile ma pudełek, i potrafi dokładać nowe pudełka na końcu, kiedy dopisujesz tekst. Nie musisz więc z góry zgadywać rozmiaru, jak przy tablicy.
string s = "kotek";
cout << s << "\n"; // cały napis
cout << s.length() << "\n"; // ile ma znaków
cout << s[0] << "\n"; // pierwszy znak
cout << s[4] << "\n"; // ostatni znak
cout << s[1] << s[2] << "\n"; // drugi i trzeci, jeden za drugim
Prześledź wyjście linijka po linijce. cout << s wypisuje cały napis naraz — tego tablica nie potrafiła. s.length() mówi, ile jest pudełek: 5.
s[0] to pierwsze pudełko, a s[4] — ostatnie. W słowie „kotek” oba zawierają literę k, dlatego w wyjściu są dwa k pod rząd.
Ostatnia linijka wypisuje dwa znaki jeden za drugim: s[1] to o, a s[2] to t. Między nimi nie ma spacji, bo żadnej nie wypisaliśmy.
s[0], s[1], …, s[n - 1]. Pierwszy znak to zawsze s[0], a ostatni — s[n - 1], czyli s[s.length() - 1]. Pudełka s[n] już nie ma. To dokładnie ta sama zasada co w tablicach.
Długość: length() i size()
Długość napisu to liczba jego znaków. Liczą się wszystkie znaki: litery, cyfry, kropki, wykrzykniki — i spacje. Spacja to pełnoprawny znak, który zajmuje swoje pudełko. Na rysunkach będziemy ją pokazywać jako ␣, żeby było ją widać.
string a = "Ala ma kota";
string b = ""; // pusty napis — zero znaków
string c = " "; // jedna spacja
string d = "?!";
cout << a.length() << "\n";
cout << b.length() << "\n";
cout << c.length() << "\n";
cout << d.size() << "\n"; // size() to to samo co length()
length() i size() robią dokładnie to samo — możesz używać, którego chcesz. W wielu programach olimpijskich zobaczysz size(), bo tak samo nazywa się długość w innych strukturach, które poznasz później.
Zwróć uwagę na napis b. Dwa cudzysłowy bez niczego w środku to napis pusty — prawdziwy napis, który ma zero znaków. A c to nie pusty napis, tylko napis z jedną spacją. Na ekranie wyglądają tak samo, ale mają różne długości.
Nawiasy po length są obowiązkowe. Bez nich kompilator zgłosi błąd.
Pusty napis i empty()
Gdy tworzysz napis bez wartości — string s; — dostajesz napis pusty. To ważna różnica względem int: zmienna liczbowa utworzona w main bez wartości zawiera śmieci, a napis zawsze zaczyna jako pusty. Czy napis jest pusty, sprawdzisz metodą empty(). Zwraca prawdę albo fałsz, więc nadaje się prosto do if.
string s; // bez wartości — pusty
cout << s.length() << "\n";
cout << s.empty() << "\n"; // 1, czyli prawda
s = "a";
cout << s.empty() << "\n"; // 0, czyli fałsz
if (s.empty()) {
cout << "pusto\n";
} else {
cout << "jest tekst\n";
}
Zapis s.empty() czytaj: „czy napis s jest pusty?”. Pamiętasz z lekcji o typach, że cout wypisuje prawdę jako 1, a fałsz jako 0.
Zamiast s.empty() możesz napisać s.length() == 0 albo s == "" — znaczą to samo. empty() jest po prostu najkrótsze i najczytelniejsze.
Pusty napis przyda się bardzo często jako punkt startowy: zaczynasz od "" i dokładasz kolejne znaki. Tak będziemy budować napisy w części 4.
Pierwszy, ostatni i środkowy znak
Te trzy pozycje pojawiają się w zadaniach bez przerwy, więc warto mieć je w małym palcu. Najwygodniej najpierw zapisać długość w zmiennej n — za chwilę zobaczysz, że to nie tylko wygoda.
string s = "programowanie";
int n = s.length(); // 13
cout << s[0] << "\n"; // pierwszy
cout << s[n - 1] << "\n"; // ostatni
cout << s[n / 2] << "\n"; // środkowy: s[6]
cout << s.front() << s.back() << "\n";
Dla nieparzystej długości środek jest jeden: przed nim i za nim stoi tyle samo znaków. W słowie o 13 znakach to pudełko 6 — przed nim pudełka 0–5, za nim 7–12, po sześć z każdej strony. Dzielenie całkowite n / 2 daje właśnie 6.
Dla parzystej długości środkowe są dwa: s[n / 2 - 1] i s[n / 2]. Sprawdź na kartce: w słowie „domek” (5 liter) środkiem jest m, a w słowie „okno” (4 litery) środkowe są k i n.
s.front() i s.back() to skróty: pierwszy i ostatni znak. Działają tylko dla napisu, który nie jest pusty.
Zmiana jednego znaku
Pudełko napisu zachowuje się jak zwykła zmienna typu char. Możesz do niego wpisać nowy znak przez =. Napis zmienia się w tym jednym miejscu, a długość zostaje taka sama. Prześledź program w tabelce obok — w każdej linijce zmienia się dokładnie jedno pudełko.
string s = "kot";
s[0] = 'p'; // k zamienia się w p
cout << s << "\n";
s[2] = 'r'; // t zamienia się w r
cout << s << "\n";
s[1] = s[0]; // drugie pudełko dostaje kopię pierwszego
cout << s << "\n";
| po linijce | s[0] | s[1] | s[2] | s |
|---|---|---|---|---|
string s = "kot"; | k | o | t | kot |
s[0] = 'p'; | p | o | t | pot |
s[2] = 'r'; | p | o | r | por |
s[1] = s[0]; | p | p | r | ppr |
Znak wpisujesz w apostrofach: 'p'. Zapis s[0] = "p"; się nie skompiluje — w cudzysłowie jest napis, a do pudełka mieści się tylko jeden znak.
Przez s[i] = … możesz tylko podmienić istniejący znak. Nowego pudełka na końcu tak nie dodasz: w trzyznakowym napisie s[3] = 'y'; to błąd. Dokładanie znaków poznasz w części 4.
Napis tworzony na różne sposoby
Napis możesz utworzyć na kilka sposobów. Pięć z nich znasz już z lekcji o typach, szósty jest nowy. W programie obok każdy napis wypisujemy w nawiasach kwadratowych — to prosty trik, dzięki któremu widać, gdzie napis się zaczyna i kończy, nawet gdy jest pusty albo kończy się spacją.
string a; // pusty
string b = "tekst"; // z gotowym tekstem
string c(4, '*'); // 4 razy ten sam znak
string d = b; // kopia napisu b
string e = b + "!"; // sklejony z dwóch kawałków
string f(1, 'x'); // napis z jednego znaku
cout << "[" << a << "]\n";
cout << "[" << b << "]\n";
cout << "[" << c << "]\n";
cout << "[" << d << "]\n";
cout << "[" << e << "]\n";
cout << "[" << f << "]\n";
string c(4, '*'); to ten sam przepis co string(4, '*') z lekcji o typach: „zrób napis z czterech gwiazdek”. Najpierw liczba, potem znak w apostrofach.
string f(1, 'x'); wygląda dziwnie, ale bywa potrzebny: robi napis z jednego znaku. Znak 'x' i napis "x" to w C++ różne rzeczy — w części 4 zobaczysz, kiedy ta różnica gryzie.
Nawiasy kwadratowe w cout nie są częścią napisów — to zwykły tekst, który wypisujemy dookoła. Używaj tego triku zawsze, gdy nie masz pewności, co naprawdę jest w napisie.
Kopiowanie i porównywanie — tu napis wygrywa z tablicą
Z lekcji o tablicach pamiętasz, że tablicy nie da się skopiować znakiem =, a a == b nie porównuje jej zawartości. Z napisami jest dużo wygodniej: = robi pełną kopię, a == porównuje tekst znak po znaku. Kopia jest osobnym napisem — zmiana kopii nie rusza oryginału.
string a = "kot";
string b = a; // b to osobna kopia
b[0] = 'p'; // zmieniamy tylko b
cout << a << " " << b << "\n";
cout << (a == b) << "\n"; // czy takie same?
b[0] = 'k';
cout << (a == b) << "\n";
Po b = a oba napisy zawierają „kot”, ale leżą w osobnych pudełkach. Zmiana b[0] zmienia tylko b, więc a zostaje „kot”, a b staje się „pot”.
Porównanie a == b sprawdza, czy oba napisy mają tę samą długość i te same znaki na tych samych miejscach. Po przywróceniu b[0] = 'k' znowu są równe. Nawias wokół porównania w cout jest obowiązkowy — pamiętasz to z lekcji o typach.
Porównywaniem napisów — także tym, który jest „mniejszy” — zajmiemy się dokładnie w części 5.
Poza napisem — ten sam błąd co w tablicy
Co się stanie, gdy sięgniesz po pudełko, którego nie ma, na przykład s[5] w trzyznakowym napisie? Dokładnie to samo co w tablicy: C++ nie sprawdza numeru. Nie zobaczysz komunikatu. Dostaniesz przypadkowy znak z pamięci obok albo program się wysypie — czasem dopiero w sprawdzarce.
Napis ma jednak bezpieczniejszą wersję nawiasów: metodę at. Zapis s.at(i) działa jak s[i], ale najpierw sprawdza, czy pudełko i istnieje. Jeśli nie — zatrzymuje program z komunikatem o błędzie zamiast udawać, że wszystko gra.
string s = "kot";
cout << s[5] << "\n"; // BŁĄD: nie ma pudełka 5 — wynik przypadkowy
cout << s.at(5) << "\n"; // at() sprawdza numer i zatrzymuje program
at zatrzymał program i powiedział wprost: pytasz o pudełko 5, a napis ma rozmiar 3. Gdy Twój program daje dziwne wyniki, zamień na chwilę s[i] na s.at(i) — jeśli gdzieś wychodzisz poza napis, od razu się dowiesz. W gotowym rozwiązaniu możesz wrócić do zwykłych nawiasów.
Pułapka: długość nie zna liczb ujemnych
Teraz rzecz, która zaskakuje prawie każdego. Liczba zwracana przez s.length() ma specjalny typ, który nie ma liczb ujemnych — taki typ nazywa się „bez znaku” (po angielsku unsigned). Co się dzieje, gdy od zera w takim typie odejmiesz jeden? Wynik „przekręca się” jak licznik kilometrów w starym samochodzie: po 0000 cofnięciu wychodzi 9999. Tu wychodzi największa liczba, jaką ten typ mieści.
string s = ""; // pusty, długość 0
cout << s.length() - 1 << "\n"; // 0 - 1 w typie bez znaku
int n = s.length(); // długość w zwykłym int
cout << n - 1 << "\n"; // teraz -1, tak jak trzeba
Pierwsza linijka wyniku to nie żart: 18 446 744 073 709 551 615, czyli 264 − 1. Tyle wychodzi z 0 − 1, gdy liczba nie może być ujemna.
Czym to grozi? Pętla for (int i = 0; i < s.length() - 1; i++) dla pustego napisu wykonałaby się miliardy razy i wyszła daleko poza napis. To bardzo częsty powód błędu wykonania w sprawdzarce.
Najprostsza ochrona: na początku zapisz długość w zmiennej int n = s.length(); i dalej używaj n. W zwykłym int zero minus jeden to po prostu −1. Przy okazji znikną ostrzeżenia kompilatora o porównywaniu liczb „ze znakiem i bez znaku”.
Polskie litery to dwa znaki
Na koniec obiecane wyjaśnienie, dlaczego w zadaniach nie ma polskich liter. Komputer zapisuje znaki z ogonkami — ą, ć, ę, ł, ń, ó, ś, ź, ż — za pomocą dwóch bajtów, a string liczy bajty, nie litery. Słowo „żółw” ma dla nas cztery litery, ale dla C++ siedem znaków: ż, ó i ł zajmują po dwa pudełka, a w — jedno.
string s = "żółw";
cout << s.length() << "\n";
Z tego samego powodu s[0] to tylko połowa litery ż — wypisany osobno pokaże się jako dziwny znaczek, a toupper w ogóle go nie zmieni. Dlatego w zadaniach olimpijskich (także na OI i OIJ) teksty składają się ze zwykłych liter od a do z — i tak samo jest we wszystkich zadaniach tej lekcji.
Jeśli testujesz program u siebie, wpisuj dane bez polskich liter: „zolw”, a nie „żółw”.
Najpierw odpowiedz w myślach — rozpisz sobie znaki napisu w pudełkach z numerami i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.
string s = "olimpiada";
cout << s.length() << " " << s[3];
Pokaż odpowiedź
s[0] = o, s[1] = l, s[2] = i, s[3] = m.string s = "Ala ma kota.";
cout << s.length();
Pokaż odpowiedź
string s = "mama";
s[0] = 'l';
s[2] = 'l';
cout << s;
Pokaż odpowiedź
string s = "abc";
string t = s;
t[1] = 'X';
cout << s << t;
Pokaż odpowiedź
t to osobna kopia, więc zmiana t[1] nie rusza s. Wypisujemy „abc”, a zaraz za nim „aXc”.string s(3, 'o');
cout << s + "k" << " " << s.length();
Pokaż odpowiedź
s to „ooo”. s + "k" tworzy nowy napis „oook” do wypisania, ale samego s nie zmienia — jego długość to nadal 3.string s = "programista";
int n = s.length();
cout << s[n - 2] << s[n / 2];
Pokaż odpowiedź
s[9] to t (przedostatnia litera), a s[11 / 2] = s[5] to a: p-r-o-g-r-a.string s;
cout << s.empty() << s.length();
Pokaż odpowiedź
empty() daje prawdę (1), a długość to 0. Wypisane bez spacji dają „10”.string a = "Kot";
string b = "kot";
cout << (a == b);
Pokaż odpowiedź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
Wczytywanie tekstu na każdy sposób
W zadaniach napis prawie nigdy nie jest wpisany w program — przychodzi z wejścia. Czasem to jedno słowo, czasem całe zdanie ze spacjami, a czasem cały tekst z wieloma wierszami, o którym nie wiesz nawet, ile ma słów. W tej części poukładamy wszystkie sposoby wczytywania tekstu. Część z nich znasz z lekcji Input / Output — teraz zobaczysz je razem i dowiesz się, kiedy który wybrać.
Słowo czy cały wiersz?
Podstawowe pytanie brzmi: czy spacja ma kończyć napis, czy nie? Spójrz na dwa programy, które dostają to samo wejście.
string s;
cin >> s; // jedno słowo
cout << "[" << s << "]\n";
string s;
getline(cin, s); // cały wiersz
cout << "[" << s << "]\n";
| zapis | co wczytuje | spacje i Entery |
|---|---|---|
cin >> s; | jedno słowo — ciąg znaków bez odstępów | na początku je pomija, a na pierwszym odstępie po słowie się zatrzymuje |
getline(cin, s); | cały wiersz — wszystko aż do Entera | spacje trafiają do napisu; Enter jest zabierany z wejścia, ale do napisu nie trafia |
Odstęp to spacja, tabulator albo Enter. Dla cin >> wszystkie trzy znaczą to samo: „tu kończy się słowo”. Dlatego cin >> nie przejmuje się tym, ile spacji jest między słowami ani czy słowa leżą w jednym wierszu, czy w kilku:
string a, b, c;
cin >> a >> b >> c;
cout << a << "|" << b << "|" << c << "\n";
Pięć spacji po „Ala”, a potem pusty wiersz — cin >> po prostu je przeskakuje i bierze kolejne słowa. W napisach nie ma żadnych spacji ani Enterów.
To bardzo wygodne, gdy dane to słowa. Ale gdy spacje są ważne — imię i nazwisko, zdanie, adres — potrzebujesz getline.
Słowa aż do końca danych
Często zadanie nie mówi, ile będzie słów: „wczytaj tekst i policz w nim słowa”. Znasz już na to sposób z lekcji o pętli while — while (cin >> x). Działa tak samo dla napisów: dopóki udaje się wczytać kolejne słowo, warunek jest prawdziwy, a gdy dane się skończą — fałszywy i pętla się kończy.
string s;
int ile = 0;
while (cin >> s) { // wczytaj kolejne słowo, dopóki się da
ile++;
}
cout << ile << "\n";
string s, najdluzsze = "";
while (cin >> s) {
if (s.length() > najdluzsze.length()) {
najdluzsze = s;
}
}
cout << najdluzsze << "\n";
Zauważ dwie rzeczy. Po pierwsze, „słowo” dla cin >> to wszystko między odstępami — razem z przecinkami i wykrzyknikami. „Litwo,” ma 6 znaków, a „moja!” — 5. Po drugie, w prawym programie zaczynamy od pustego napisu, więc pierwsze słowo zawsze okaże się dłuższe. Przy remisie zostaje słowo wcześniejsze, bo warunek to >, a nie >= — to ten sam schemat co rekord z lekcji o tablicach.
Wiersz po wierszu
getline też można zapętlić. while (getline(cin, linia)) wczytuje kolejne wiersze aż do końca danych. W odróżnieniu od cin >> nie pomija pustych wierszy — pusty wiersz to po prostu napis o długości 0.
string linia;
int nr = 0;
while (getline(cin, linia)) {
nr++;
cout << nr << ": " << linia << " (" << linia.length() << ")\n";
}
Każdy obrót pętli to jeden wiersz wejścia, razem ze spacjami. Trzeci wiersz jest pusty, więc program wypisuje numer, pusty napis i długość 0.
Gdybyś chciał pomijać puste wiersze, wystarczy na początku obrotu dopisać:
if (linia.empty()) {
continue;
}
Liczba, a potem wiersz — pułapka z Enterem
Ta pułapka pojawiła się już w lekcji Input / Output, ale jest tak częsta, że musimy ją powtórzyć. Wejście wygląda tak: w pierwszym wierszu liczba, w drugim zdanie. Po cin >> n na taśmie wejścia zostaje Enter, który kończył pierwszy wiersz. getline czyta „do Entera” — a Enter leży od razu na początku. Wczytuje więc pusty napis i kończy pracę.
int n;
string zdanie;
cin >> n;
getline(cin, zdanie); // wczyta pusty kawałek po liczbie!
cout << n << " [" << zdanie << "]\n";
int n;
string zdanie;
cin >> n;
cin.ignore(); // zjedz Enter po liczbie
getline(cin, zdanie);
cout << n << " [" << zdanie << "]\n";
cin.ignore() zabiera z wejścia jeden znak — właśnie ten Enter. Jest też drugi sposób, odporny nawet na spacje zostawione za liczbą: getline(cin >> ws, zdanie);. ws pomija wszystkie odstępy (spacje i Entery), a getline zaczyna czytać od pierwszego prawdziwego znaku. Uwaga: ws zje też spacje na początku zdania, więc używaj go tylko wtedy, gdy wiersz nie zaczyna się od ważnych spacji.
Najczęstszy układ w zadaniach to liczba n, a potem n wierszy tekstu. cin.ignore() wystarczy wtedy raz, zaraz po liczbie — kolejne getline same zabierają swoje Entery:
int n;
cin >> n;
cin.ignore();
for (int i = 1; i <= n; i++) {
string linia;
getline(cin, linia);
cout << i << ". " << linia << "\n";
}
cin >>. Dane to wiersze, w których spacje są ważne — getline. Mieszasz oba sposoby i po cin >> przychodzi getline — między nimi cin.ignore() (albo cin >> ws). Odwrotna kolejność jest bezpieczna: cin >> po getline sam pominie odstępy.
Tablica napisów
Gdy słowa trzeba zapamiętać — żeby wypisać je od końca albo porównać z czymś wczytanym później — wkładasz je do tablicy napisów, tak jak w lekcji o tablicach. Każde pudełko t[i] zawiera cały napis.
string t[100];
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> t[i];
}
for (int i = n - 1; i >= 0; i--) {
cout << t[i] << " ";
}
cout << "\n";
string t[3] = {"Polski", "Zwiazek", "Wedkarski"};
for (int i = 0; i < 3; i++) {
cout << t[i][0]; // pierwsza litera i-tego słowa
}
cout << "\n";
cout << t[1][2] << "\n"; // trzecia litera drugiego słowa
Prawy program pokazuje nowy zapis z dwoma nawiasami kwadratowymi. t[i] to cały napis numer i, a skoro to napis, to jego znak numer j to t[i][j]. Czytaj od lewej: „z tablicy t weź słowo i, a z tego słowa — znak j”. t[1] to „Zwiazek”, więc t[1][2] to jego trzecia litera, i.
Wiersz pocięty przecinkami
Czasem kawałki tekstu nie są oddzielone spacjami, tylko innym znakiem, na przykład przecinkiem: Ola,Jan,Ewa. cin >> wczytałby to jako jedno słowo. Są na to dwa sposoby. Pierwszy znasz z lekcji Input / Output: getline z trzecim argumentem czyta do wskazanego znaku zamiast do Entera.
string imie;
while (getline(cin, imie, ',')) {
cout << "- " << imie << "\n";
}
string linia, kawalek = "";
getline(cin, linia);
for (char c : linia) {
if (c == ',') {
cout << "- " << kawalek << "\n";
kawalek = ""; // zaczynamy nowy kawałek
} else {
kawalek += c; // dokładamy znak do kawałka
}
}
cout << "- " << kawalek << "\n"; // ostatni kawałek
Lewy sposób jest krótszy, ale ma haczyk: ostatni kawałek kończy się nie przecinkiem, tylko Enterem — i ten Enter trafia do napisu, jeśli w danych jest. Prawy sposób jest odporny: najpierw wczytujemy cały wiersz, a potem sami idziemy po nim znak po znaku. Gdy trafiamy na przecinek, kawałek jest gotowy; każdy inny znak doklejamy do kawałka. Po pętli zostaje ostatni kawałek — po nim nie było przecinka, więc trzeba go wypisać osobno. Ten schemat cięcia wiersza przyda się jeszcze wiele razy, a w części 6 poznasz trzeci sposób, z find i substr.
Najpierw odpowiedz w myślach — przy każdym pytaniu wyobraź sobie taśmę wejścia i to, co zabiera z niej każda instrukcja — a dopiero potem kliknij „Pokaż odpowiedź”.
string a, b;
cin >> a >> b;
cout << b << a;
Ala ma kotaPokaż odpowiedź
cin >> czyta po jednym słowie: a to „Ala”, b to „ma”. „kota” zostaje na wejściu nieprzeczytane. Wypisujemy b, a zaraz za nim a — bez spacji.string s;
getline(cin, s);
cout << s.length();
Ala ma kotaPokaż odpowiedź
getline wczytuje cały wiersz razem ze spacjami: 9 liter i 2 spacje.int n;
string s;
cin >> n;
getline(cin, s);
cout << s.length();
5 Ala ma kotaPokaż odpowiedź
getline wczytuje pusty napis. Brakuje cin.ignore().string s;
int k = 0;
while (cin >> s) {
k++;
}
cout << k;
raz dwa trzy czteryPokaż odpowiedź
cin >> czyta słowa i nie przejmuje się Enterami: raz, dwa, trzy, cztery.string s;
int k = 0;
while (getline(cin, s)) {
k++;
}
cout << k;
raz dwa trzy czteryPokaż odpowiedź
getline czyta całe wiersze, a wiersze są dwa: „raz dwa trzy” i „cztery”.string t[3] = {"kot", "pies", "mysz"};
cout << t[1][0] << t[2][3];
Pokaż odpowiedź
t[1] to „pies”, a jego pierwsza litera to p. t[2] to „mysz”, a jej znak numer 3 (czwarty) to z.string s;
int k = 0;
while (getline(cin, s, ',')) {
k++;
}
cout << k;
a,bb,,cccPokaż odpowiedź
string imie, reszta;
cin >> imie;
getline(cin, reszta);
cout << "[" << reszta << "]";
Jan KowalskiPokaż odpowiedź
cin >> zatrzymuje się przed spacją po „Jan”. getline czyta resztę wiersza od tego miejsca — razem ze spacją na początku.8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
Znak po znaku: rodzaje znaków i liczniki
Większość zadań z napisami sprowadza się do tego samego: przejdź po napisie znak po znaku i przy każdym znaku zadaj pytanie. Czy to litera? Cyfra? Wielka czy mała? Taka sama jak poprzednia? W tej części nauczysz się zadawać takie pytania szybko i bez pomyłek — warunkami na przedziałach i gotowymi funkcjami z biblioteki <cctype>.
Dwie pętle po napisie — przypomnienie
Z lekcji o pętli for znasz dwa sposoby przejścia po napisie. Oba w programach poniżej liczą, ile razy w tekście występuje litera a.
string s = "ala ma kota";
int n = s.length();
int ile = 0;
for (int i = 0; i < n; i++) {
if (s[i] == 'a') {
ile++;
}
}
cout << ile << "\n";
string s = "ala ma kota";
int ile = 0;
for (char c : s) { // dla każdego znaku c z napisu s
if (c == 'a') {
ile++;
}
}
cout << ile << "\n";
Lewa pętla zna numer znaku (i), prawa — tylko sam znak (c). Zasada wyboru jest prosta: gdy potrzebujesz pozycji (wypisać, gdzie coś jest), sąsiadów (s[i - 1], s[i + 1]) albo chcesz zmieniać napis — bierz pętlę z indeksem. Gdy tylko oglądasz każdy znak po kolei — pętla „dla każdego” jest krótsza i nie da się w niej wyjść poza napis.
Jaki to znak? Warunki na przedziałach
W tabeli ASCII małe litery stoją jedna za drugą (od 97 do 122), wielkie też (od 65 do 90), cyfry też (od 48 do 57). Dlatego pytanie „czy to mała litera?” to pytanie „czy kod znaku leży między kodem a i kodem z?”. Nie musisz znać kodów — porównujesz ze znakami w apostrofach, a C++ sam podstawi liczby.
| warunek | prawdziwy, gdy c to… | przykłady |
|---|---|---|
c >= 'a' && c <= 'z' | mała litera | a, k, z |
c >= 'A' && c <= 'Z' | wielka litera | A, K, Z |
c >= '0' && c <= '9' | cyfra | 0, 5, 9 |
c == ' ' | spacja | ␣ |
c == 'a' || c == 'e' || … | jeden z wymienionych znaków | samogłoski: a, e, i, o, u, y |
Ten sposób znasz z lekcji o if. Działa zawsze i jest całkowicie przewidywalny. Ma jedną wadę: warunki są długie i łatwo w nich o literówkę — na przykład c >= 'a' && c <= 'Z' z jedną wielką literą przez pomyłkę. Dlatego C++ ma gotowe funkcje.
Gotowe funkcje: isdigit, isalpha i spółka
Biblioteka <cctype> (jest też w <bits/stdc++.h>) zawiera funkcje, które odpowiadają na pytania o rodzaj znaku. Ich nazwy zaczynają się od is — po angielsku „czy jest”. isdigit(c) czytaj: „czy c jest cyfrą?”.
| funkcja | prawda, gdy c to… | to samo co |
|---|---|---|
isdigit(c) | cyfra od 0 do 9 | c >= '0' && c <= '9' |
islower(c) | mała litera | c >= 'a' && c <= 'z' |
isupper(c) | wielka litera | c >= 'A' && c <= 'Z' |
isalpha(c) | litera, mała albo wielka | islower(c) || isupper(c) |
isalnum(c) | litera albo cyfra | isalpha(c) || isdigit(c) |
isspace(c) | odstęp: spacja, tabulator, Enter | c == ' ' || c == '\t' || c == '\n' … |
ispunct(c) | znak przestankowy: . , ! ? : ; - ( ) itd. | — |
string s;
getline(cin, s);
int litery = 0, cyfry = 0, spacje = 0, inne = 0;
for (char c : s) {
if (isalpha(c)) {
litery++;
} else if (isdigit(c)) {
cyfry++;
} else if (isspace(c)) {
spacje++;
} else {
inne++;
}
}
cout << litery << " " << cyfry << " " << spacje << " " << inne << "\n";
Cztery liczniki i łańcuch else if: każdy znak trafia do dokładnie jednej grupy. Litery: A, l, a, m, a, k, o, t, y — dziewięć. Cyfra jedna (2), spacje trzy, a „inne” to wykrzyknik.
Kolejność warunków ma znaczenie tylko wtedy, gdy grupy się nakładają. Tu się nie nakładają, więc mogłyby stać w dowolnej kolejności — ale else na końcu musi zostać ostatni, bo łapie wszystko, czego nie złapały warunki przed nim.
is… zwracają int: zero, gdy odpowiedź brzmi „nie”, i jakąś liczbę różną od zera, gdy „tak” — niekoniecznie 1! Na serwerze sprawdzarki isalpha('k') to 1024, na Twoim komputerze może wyjść na przykład 258 albo 2. W warunkach if i while to bez znaczenia, bo każda liczba różna od zera liczy się jako prawda. Ale nie porównuj ich wyniku z 1 ani z true i nie wypisuj go — pisz po prostu if (isalpha(c)) albo if (!isalpha(c)).
cout << isalpha('k') << "\n"; // liczba różna od zera
cout << isalpha('7') << "\n"; // 0
if (isalpha('k')) {
cout << "to litera\n";
}
if (isalpha('k') == true) { // ŹLE: 1024 to nie 1
cout << "tego nie zobaczysz\n";
}
Pierwszy if działa: 1024 to „nie zero”, więc prawda. Drugi nie działa, choć wygląda niewinnie: true w porównaniu z liczbą zamienia się na 1, a 1024 to nie 1.
Jeśli naprawdę potrzebujesz zera albo jedynki — na przykład żeby dodać wynik do licznika — zamień go na bool: ile += (isalpha(c) != 0);. Ale prościej i czytelniej jest napisać zwykły if z ile++.
toupper i tolower — zmiana wielkości litery
W lekcji o typach zamieniałeś małą literę na wielką rachunkiem c - 'a' + 'A'. Gotowe funkcje robią to samo prościej: toupper(c) daje wielką wersję litery („to upper” — na wielką), a tolower(c) — małą. Znaki, które nie są literami, zwracają bez zmian. Jest tylko jedna pułapka — ta sama co przy is…: wynik to int.
char c = 'k';
cout << toupper(c) << "\n"; // liczba!
cout << (char)toupper(c) << "\n"; // teraz znak
char d = toupper(c); // zapis do char też daje znak
cout << d << "\n";
cout << (char)tolower('Q') << "\n";
cout << (char)toupper('7') << "\n"; // nie litera — bez zmian
cout << toupper(c) wypisuje 75 — kod litery K — bo cout widzi liczbę typu int. Żeby zobaczyć literę, zamień wynik na char: rzutowaniem (char) albo przypisaniem do zmiennej typu char.
Najczęściej i tak zapisujesz wynik z powrotem do napisu: s[i] = toupper(s[i]);. Pudełko napisu jest typu char, więc zamiana dzieje się sama i nic nie trzeba rzutować.
string s;
getline(cin, s);
int n = s.length();
for (int i = 0; i < n; i++) {
s[i] = toupper(s[i]);
}
cout << s << "\n";
char a, b;
cin >> a >> b;
if (tolower(a) == tolower(b)) {
cout << "ta sama litera\n";
} else {
cout << "rozne litery\n";
}
Prawy program pokazuje bardzo częsty trik: gdy wielkość liter ma nie mieć znaczenia, sprowadź oba znaki do małych liter i dopiero wtedy porównaj. Tutaj porównujemy dwa wyniki tolower ze sobą — oba są liczbami, więc porównanie działa bez rzutowania.
Gdzie jest pierwszy, a gdzie ostatni?
Szukanie w napisie wygląda tak samo jak szukanie w tablicy. Zaczynasz od pozycji „nie znaleziono”, czyli -1, i idziesz pętlą z indeksem. Pierwsze wystąpienie: zapisz pozycję i przerwij pętlę przez break. Ostatnie: zapisuj pozycję za każdym razem i nie przerywaj — na końcu zostanie ostatnia.
string s;
cin >> s;
int n = s.length();
int pierwsza = -1, ostatnia = -1;
for (int i = 0; i < n; i++) {
if (isdigit(s[i])) {
pierwsza = i;
break; // pierwsza znaleziona — koniec
}
}
for (int i = 0; i < n; i++) {
if (isdigit(s[i])) {
ostatnia = i; // nadpisujemy aż do końca
}
}
cout << pierwsza << " " << ostatnia << "\n";
Ostatnie wystąpienie można też znaleźć szybciej: idąc pętlą od końca, od i = n - 1 w dół, i przerywając na pierwszej cyfrze. Oba sposoby są dobre.
Wartość -1 to umówiony znak „nie ma” — żaden prawdziwy indeks nie jest ujemny, więc nie da się go pomylić z pozycją.
Sąsiednie znaki: s[i] i s[i + 1]
Wiele pytań dotyczy par sąsiadów: ile jest podwójnych liter, czy po samogłosce stoi spółgłoska, czy litery rosną. Tak samo jak w tablicy pętla musi wtedy kończyć się wcześniej: i < n - 1, bo przy ostatnim znaku nie ma już s[i + 1]. Tu przydaje się n typu int — dla pustego napisu n - 1 to −1 i pętla się po prostu nie wykona.
string s;
cin >> s;
int n = s.length();
int ile = 0;
for (int i = 0; i < n - 1; i++) {
if (s[i] == s[i + 1]) {
ile++;
}
}
cout << ile << "\n";
string s;
cin >> s;
int n = s.length();
int zmiany = 0; // ile razy wielkość litery się zmienia
for (int i = 1; i < n; i++) {
if (isupper(s[i]) && islower(s[i - 1])) zmiany++;
if (islower(s[i]) && isupper(s[i - 1])) zmiany++;
}
cout << zmiany << "\n";
Prawy program patrzy w drugą stronę: na znak i jego poprzednika. Wtedy pętla startuje od i = 1, bo pierwszy znak poprzednika nie ma. Dwie wersje — s[i] z s[i + 1] do n - 1 albo s[i] z s[i - 1] od 1 — sprawdzają dokładnie te same pary. Wybierz tę, która lepiej pasuje do zadania.
Serie: ten sam znak pod rząd
Seria to kilka takich samych znaków stojących obok siebie, na przykład bbbb w „aaabbbbcc”. Jak znaleźć najdłuższą serię? Idziemy po napisie i pamiętamy długość bieżącej serii. Jeśli znak jest taki sam jak poprzedni — seria rośnie. Jeśli inny — zaczyna się nowa seria o długości 1. Po każdym kroku sprawdzamy, czy pobiliśmy rekord.
string s;
cin >> s;
int n = s.length();
int dlugosc = 1, rekord = 1;
char znak = s[0];
for (int i = 1; i < n; i++) {
if (s[i] == s[i - 1]) {
dlugosc++; // seria trwa
} else {
dlugosc = 1; // nowa seria
}
if (dlugosc > rekord) {
rekord = dlugosc;
znak = s[i];
}
}
cout << znak << " " << rekord << "\n";
| i | s[i] | s[i − 1] | dlugosc | rekord |
|---|---|---|---|---|
| start | — | — | 1 | 1 (a) |
| 1 | a | a | 2 | 2 (a) |
| 2 | a | a | 3 | 3 (a) |
| 3 | b | a | 1 | 3 (a) |
| 4 | b | b | 2 | 3 (a) |
| 5 | b | b | 3 | 3 (a) |
| 6 | b | b | 4 | 4 (b) |
| 7 | c | b | 1 | 4 (b) |
| 8 | c | c | 2 | 4 (b) |
Ten program zakłada, że napis nie jest pusty — czyta s[0] na samym początku. W zadaniu zawsze sprawdź, czy ograniczenia to gwarantują.
Flagi: czy jest choć jeden? czy wszystkie?
Dwa pytania pojawiają się bez przerwy: „czy w napisie jest choć jeden znak taki-a-taki?” i „czy wszystkie znaki są takie-a-takie?”. Oba rozwiązuje flaga, czyli zmienna bool z lekcji o if. Dla „choć jeden” startujesz od false i zmieniasz na true, gdy znajdziesz pasujący znak. Dla „wszystkie” — odwrotnie: startujesz od true i zmieniasz na false przy pierwszym znaku, który nie pasuje.
string s;
cin >> s;
bool jestCyfra = false; // czy choć jeden znak to cyfra
bool sameLitery = true; // czy wszystkie znaki to litery
for (char c : s) {
if (isdigit(c)) {
jestCyfra = true;
}
if (!isalpha(c)) {
sameLitery = false;
}
}
cout << jestCyfra << " " << sameLitery << "\n";
!isalpha(c) — wykrzyknik odwraca odpowiedź: „c nie jest literą”. Gdy flaga raz się zmieni, już nie wraca, więc możesz od razu wyjść z pętli przez break — chyba że w tej samej pętli liczysz jeszcze coś innego, jak tutaj.
Najpierw odpowiedz w myślach — rozpisz sobie znaki napisu w pudełkach z numerami i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.
string s = "a1b2c3";
int k = 0;
for (char c : s) {
if (isdigit(c)) k += c - '0';
}
cout << k;
Pokaż odpowiedź
c - '0' zamienia znak cyfry na jej wartość: 1 + 2 + 3 = 6.cout << (char)toupper('b') << toupper('b');
Pokaż odpowiedź
char widać literę B. Bez rzutowania toupper daje int — kod litery B, czyli 66.string s = "Hello World";
int k = 0;
for (char c : s) {
if (isupper(c)) k++;
}
cout << k;
Pokaż odpowiedź
string s = "aabbbab";
int n = s.length(), k = 0;
for (int i = 0; i < n - 1; i++) {
if (s[i] == s[i + 1]) k++;
}
cout << k;
Pokaż odpowiedź
string s = "Kot i PIES";
for (char &c : s) {
c = tolower(c);
}
cout << s;
Pokaż odpowiedź
& zmieniamy prawdziwe znaki napisu. Spacje i małe litery tolower zostawia bez zmian.string s = "abcabc";
int p = -1;
for (int i = 0; i < 6; i++) {
if (s[i] == 'b') p = i;
}
cout << p;
Pokaż odpowiedź
break, więc p jest nadpisywane przy każdym b: najpierw 1, potem 4. Zostaje ostatnie.char c = 'z';
c = toupper(c) + 1;
cout << c;
Pokaż odpowiedź
toupper('z') to kod litery Z, czyli 90. Plus 1 daje 91 — a pod numerem 91 w tabeli ASCII stoi nawias kwadratowy. Za Z nie ma już liter!string s = "abc!";
bool ok = true;
for (char c : s) {
if (!islower(c)) ok = false;
}
cout << ok;
Pokaż odpowiedź
false.8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
Zmieniamy i budujemy napisy
Z napisem możesz pracować na dwa sposoby. Pierwszy: zmieniasz znaki w miejscu, pudełko po pudełku. Napis ma wtedy cały czas tę samą długość — każdy znak zamienia się na inny. Drugi: budujesz nowy napis od pustego, dokładając kawałek po kawałku. Wtedy możesz robić, co chcesz: pomijać znaki, podwajać je, wstawiać nowe. W tej części przećwiczymy oba sposoby i poznamy pułapki, które czyhają przy sklejaniu.
Zmiana w miejscu
Do zmiany w miejscu wystarczy pętla z indeksem i przypisanie s[i] = …. Albo pętla „dla każdego” z & — pamiętasz z lekcji o pętli for, że bez & zmienna c jest tylko kopią znaku i zmiany przepadają.
string s;
getline(cin, s);
for (char &c : s) { // & — pracujemy na prawdziwych znakach
if (c == ' ') {
c = '_';
}
}
cout << s << "\n";
string s;
getline(cin, s);
int n = s.length();
for (int i = 0; i < n; i++) {
if (i == 0 || s[i - 1] == ' ') {
s[i] = toupper(s[i]); // pierwsza litera słowa
}
}
cout << s << "\n";
W prawym programie litera zaczyna słowo, gdy stoi na samym początku albo zaraz po spacji. Kolejność w warunku i == 0 || s[i - 1] == ' ' jest bardzo ważna. Pamiętasz z lekcji o if skrócone obliczanie? Gdy i == 0 jest prawdą, C++ nie sprawdza już drugiej części — i dobrze, bo s[-1] nie istnieje. Odwrotna kolejność czytałaby poza napisem.
Budowanie od pustego napisu: += i push_back
Drugi sposób zaczyna się od pustego napisu "". Potem dokładasz kawałki na koniec. Doklejać możesz pojedynczy znak albo cały napis — operator += przyjmie jedno i drugie. Jest też metoda push_back(c) („wepchnij na koniec”), która dokłada tylko jeden znak.
string w = ""; // zaczynamy od pustego
w += 'k'; // jeden znak
w += "ot"; // cały napis
w.push_back('y'); // push_back — jeden znak
cout << w << " " << w.length() << "\n";
| po linijce | w | długość |
|---|---|---|
string w = ""; | 0 | |
w += 'k'; | k | 1 |
w += "ot"; | kot | 3 |
w.push_back('y'); | koty | 4 |
Najczęściej budowanie odbywa się w pętli: idziesz po starym napisie i decydujesz, co z każdym znakiem zrobić w nowym. Zostawić? Pominąć? Dopisać dwa razy? Zamienić na coś innego? Ta jedna decyzja to cały program.
string s, cyfry = "";
getline(cin, s);
for (char c : s) {
if (isdigit(c)) {
cyfry += c; // cyfrę zostawiamy, resztę pomijamy
}
}
cout << cyfry << "\n";
string s, w = "";
cin >> s;
for (char c : s) {
w += c; // każdy znak
w += c; // ... dwa razy
}
cout << w << "\n";
string s, w = "";
getline(cin, s);
for (char c : s) {
if (isdigit(c)) {
w += "**"; // cyfrę zamieniamy na dwie gwiazdki
} else {
w += c;
}
}
cout << w << "\n";
Zwróć uwagę, że nowy napis może być krótszy od starego (tylko cyfry), dłuższy (podwajanie, gwiazdki) albo zupełnie inny. Przy zmianie w miejscu tak się nie da — tam długość zawsze zostaje ta sama.
Dlatego zasada jest prosta: jeśli każdy znak zamienia się na dokładnie jeden znak — zmieniaj w miejscu. Jeśli coś znika albo przybywa — buduj nowy napis.
Doklejanie z przodu
Kawałek możesz dokleić także na początek: w = c + w;. Czytaj: „nowe w to znak c, a za nim całe stare w”. Doklejanie każdego kolejnego znaku z przodu odwraca napis.
string s, w = "";
cin >> s;
for (char c : s) {
w = c + w; // nowy znak na początek
}
cout << w << "\n";
| obrót | c | w po obrocie |
|---|---|---|
| start | — | |
| 1. | a | a |
| 2. | b | ba |
| 3. | c | cba |
Zapis c + w działa, bo w jest napisem: znak plus napis daje napis. Ale uwaga — doklejanie z przodu jest wolne: za każdym razem komputer przepisuje cały napis o jedno miejsce. Dla kilku tysięcy znaków to nic, dla miliona — za dużo. Wrócimy do tego w części 8.
Usuwanie z końca: pop_back i clear
pop_back() to odwrotność push_back: usuwa ostatni znak napisu. clear() usuwa wszystkie znaki naraz — napis staje się pusty. Typowe zastosowanie pop_back: dopisujesz separator po każdym elemencie, a na koniec usuwasz ten ostatni, niepotrzebny.
string s = "1, 2, 3, ";
s.pop_back(); // usuwa spację
s.pop_back(); // usuwa przecinek
cout << "[" << s << "]\n";
s.clear();
cout << "[" << s << "] " << s.empty() << "\n";
string s = "kot", w = "";
for (char c : s) {
w += c;
cout << w << "\n"; // rośnie: k, ko, kot
}
while (w.length() > 1) {
w.pop_back();
cout << w << "\n"; // maleje: ko, k
}
pop_back() na pustym napisie to błąd — taki sam jak wyjście poza tablicę: program może się wysypać albo zacząć robić dziwne rzeczy. Zanim zawołasz pop_back(), upewnij się, że napis nie jest pusty: if (!s.empty()) s.pop_back();.
Pułapki sklejania
Sklejanie plusem wydaje się proste, ale kryje cztery pułapki. Wszystkie biorą się z tego samego: w C++ tylko string umie się sklejać. Znak w apostrofach to tak naprawdę liczba (kod ASCII), a tekst w cudzysłowie, który nie trafił jeszcze do zmiennej string, to „surowy” tekst, który sklejać się nie umie. Plus działa jak sklejanie tylko wtedy, gdy co najmniej jedna strona jest prawdziwym napisem string.
string s = "Ala" + " ma"; // BŁĄD: żadna strona nie jest stringiem
string s = "Ala";
s += " ma"; // s jest stringiem — działa
string t = s + " kota"; // lewa strona to string — działa
cout << t << "\n";
Pułapka 1: dwa teksty w cudzysłowach. "Ala" + " ma" się nie skompiluje — po obu stronach jest surowy tekst. Wystarczy, że jedna strona będzie zmienną typu string.
string s = "ab";
cout << s[0] + s[1] << "\n"; // dwa znaki to dwie liczby: 97 + 98
string w = "";
w += s[0];
w += s[1]; // tak sklejasz znaki
cout << w << "\n";
Pułapka 2: znak plus znak to liczba. s[0] + s[1] nie skleja liter, tylko dodaje ich kody: 97 + 98 = 195. Zapis string w = s[0] + s[1]; w ogóle się nie skompiluje — z liczby nie da się zrobić napisu.
Znaki sklejasz, dokładając je po kolei do napisu (+=), albo zaczynając od napisu z jednego znaku: string(1, s[0]) + s[1].
string s = "kot";
string a = s + to_string(5); // dobrze: "kot5"
string b = s;
b += 5; // kompiluje się, ale…
cout << a << " " << a.length() << "\n";
cout << b.length() << "\n"; // też 4 znaki — ale jakie?
Pułapka 3: napis i liczba. Zapis s + 5 w ogóle się nie skompiluje — i dobrze. Gorzej z s += 5: kompiluje się bez ostrzeżenia, ale nie dokleja cyfry 5! Liczba 5 zostaje potraktowana jak kod znaku numer 5 — to niewidzialny znak sterujący. Napis ma 4 znaki, ale czwarty to nie „5”.
Liczbę doklejasz po zamianie na napis: s + to_string(5) albo s += to_string(5). Funkcję to_string znasz z lekcji o typach — a w części 7 poznasz ją dokładniej.
int x = 3;
cout << "Wynik: " + x << "\n"; // ŹLE
cout << "Wynik: " << x << "\n"; // dobrze
Pułapka 4: surowy tekst plus liczba. To najdziwniejsza z nich. "Wynik: " + 3 to nie sklejanie, tylko przesunięcie początku tekstu o 3 znaki: „Wyn” znika i wychodzi „ik: ”. Program się kompiluje i działa, tylko wypisuje bzdury.
W cout nie sklejaj niczego plusem — wypisuj kawałki po kolei przez <<. To najprostszy sposób, żeby ominąć wszystkie cztery pułapki naraz.
| zapis | co się dzieje | wynik |
|---|---|---|
s + "ma", s + 'x', 'x' + s | sklejanie — jedna strona to string | napis |
"Ala" + " ma" | dwa surowe teksty | błąd kompilacji |
'a' + 'b', s[0] + s[1] | dodawanie kodów ASCII | liczba (195) |
s + 5 | napis plus liczba | błąd kompilacji |
s += 5 | doklejenie znaku o kodzie 5 | niewidzialny znak |
"Wynik: " + 3 | przesunięcie początku tekstu | „ik: ” |
s + to_string(5) | sklejanie z napisem „5” | napis „kot5” |
Odwracanie i palindromy — dwa sposoby
Napis od tyłu możesz zbudować jako nowy napis albo odwrócić w miejscu. Nowy napis przydaje się wtedy, gdy oryginał jest jeszcze potrzebny — na przykład żeby porównać go z odwróconym i sprawdzić, czy to palindrom. Odwracanie w miejscu wygląda dokładnie tak jak w tablicy: zamieniasz parami pierwszy z ostatnim, drugi z przedostatnim i tak dalej, aż do połowy.
string s, w = "";
cin >> s;
int n = s.length();
for (int i = n - 1; i >= 0; i--) {
w += s[i]; // od ostatniego do pierwszego
}
if (w == s) {
cout << "palindrom\n";
} else {
cout << w << "\n";
}
string s;
cin >> s;
int n = s.length();
for (int i = 0; i < n / 2; i++) {
swap(s[i], s[n - 1 - i]);
}
cout << s << "\n";
Lewa pętla idzie od n - 1 w dół, więc licznik musi być zwykłym int — po zerze zejdzie do −1 i pętla się skończy. Prawa pętla zatrzymuje się w połowie: gdyby szła do końca, każdą parę zamieniłaby dwa razy i napis wróciłby do początku.
Powtarzanie: ten sam napis k razy
string(k, c) powtarza jeden znak. Żeby powtórzyć cały napis, doklejasz go w pętli. Często trzeba też coś wstawić między powtórzenia — wtedy przydaje się trik z separatorem: przed każdym powtórzeniem oprócz pierwszego.
string s, w = "";
int k;
cin >> s >> k;
for (int i = 0; i < k; i++) {
if (i > 0) {
w += "-"; // separator przed każdym oprócz pierwszego
}
w += s;
}
cout << w << "\n";
cout << string(w.length(), '=') << "\n"; // kreska tej samej długości
s[i] = … albo for (char &c : s). Znaki znikają, przybywają albo zmienia się ich kolejność — budowanie nowego napisu od "" przez +=. Znaki sklejasz zawsze z prawdziwym napisem, a liczby — po zamianie to_string.
Najpierw odpowiedz w myślach — rozpisz sobie znaki napisu w pudełkach z numerami i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.
string w = "";
w += 'a';
w += "bc";
w.push_back('d');
w.pop_back();
cout << w;
Pokaż odpowiedź
pop_back usuwa ostatnie d.string w = "x";
w = 'y' + w;
w = w + 'z';
cout << w;
Pokaż odpowiedź
'y' + w dokleja y przed x, a w + 'z' — z na końcu. W obu przypadkach jedna strona to napis, więc plus skleja.cout << 'a' + 1;
Pokaż odpowiedź
(char)('a' + 1).string s = "ab";
string w = "";
w += s[1];
w += s[0];
w += s;
cout << w;
Pokaż odpowiedź
string s = "kajak", w = "";
for (char c : s) {
w = c + w;
}
cout << (w == s);
Pokaż odpowiedź
string s = "ala";
for (char &c : s) {
c++;
}
cout << s;
Pokaż odpowiedź
& zmiany trafiają do napisu.string s = "abc";
for (char c : s) {
c = 'x';
}
cout << s;
Pokaż odpowiedź
& zmienna c jest kopią znaku. Zmieniamy kopie, a napis zostaje nietknięty.cout << "Ala ma kota" + 4;
Pokaż odpowiedź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
Porównywanie napisów: równe, mniejsze, większe
Liczby porównujesz od pierwszej lekcji: 3 < 7, 10 == 10. Napisy też można porównywać tymi samymi operatorami: ==, !=, <, >, <=, >=. Równość jest prosta. Ciekawsze jest pytanie, kiedy jeden napis jest mniejszy od drugiego. Odpowiedź: wtedy, gdy w słowniku stałby wcześniej. Zobaczysz jednak, że „słownik” komputera ma kilka niespodzianek.
== i != — czy to dokładnie ten sam tekst?
Dwa napisy są równe, gdy mają tę samą długość i na każdej pozycji ten sam znak. Wielkość liter ma znaczenie, spacje też — nawet niewidoczna spacja na końcu.
string a = "kot", b = "Kot", c = "kot ", d = "kot";
cout << (a == b) << "\n"; // K i k to różne znaki
cout << (a == c) << "\n"; // c ma spację na końcu
cout << (a == d) << "\n"; // dokładnie ten sam tekst
cout << (a != b) << "\n"; // != to „różne”
string haslo;
cin >> haslo;
if (haslo == "sezam") {
cout << "Witaj!\n";
} else {
cout << "Zle haslo\n";
}
Napis możesz porównywać ze zmienną albo z tekstem w cudzysłowie, jak w prawym programie. Hasło „Sezam” z wielkiej litery nie pasuje do „sezam” — i dobrze, tak działają prawdziwe hasła.
Kolejność słownikowa: < i >
Jak komputer decyduje, który napis jest mniejszy? Robi dokładnie to, co Ty, gdy szukasz słowa w słowniku. Porównuje pierwsze znaki. Jeśli są różne — ten napis, którego znak jest wcześniej w alfabecie, jest mniejszy, i koniec. Jeśli są takie same — przechodzi do drugich znaków, potem do trzecich i tak dalej, aż do pierwszej różnicy. Taka kolejność nazywa się leksykograficzną — od greckiego słowa lexikon, słownik.
string a = "kotek", b = "kotlet", c = "kot";
cout << (a < b) << "\n"; // e < l na pozycji 3
cout << (c < a) << "\n"; // kot to początek słowa kotek
cout << (b > c) << "\n";
cout << (a < a) << "\n"; // nic nie jest mniejsze od siebie
| pozycja | a = kotek | b = kotlet | werdykt |
|---|---|---|---|
| 0 | k | k | równe — dalej |
| 1 | o | o | równe — dalej |
| 2 | t | t | równe — dalej |
| 3 | e | l | e < l, więc a < b |
A co, jeśli jeden napis skończy się, zanim znajdziemy różnicę — jak „kot” i „kotek”? Wtedy krótszy jest mniejszy. W słowniku też „kot” stoi przed „kotek”. Pusty napis jest więc mniejszy od każdego innego.
Zwróć uwagę: długość ma znaczenie tylko wtedy, gdy krótszy napis jest początkiem dłuższego. „b” jest większe od „aaa”, choć jest krótsze — bo już pierwsze znaki się różnią, a b jest dalej w alfabecie niż a.
Wielkie litery przed małymi
Pierwsza niespodzianka. Komputer nie zna alfabetu, zna tylko kody ASCII. Wielkie litery mają kody od 65 do 90, a małe od 97 do 122. Każda wielka litera jest więc „mniejsza” od każdej małej. Dla komputera „Zebra” stoi w słowniku przed „antylopą”, bo Z (90) < a (97). Podobnie cyfry (48–57) są przed wszystkimi literami, a spacja (32) — przed cyframi.
string a = "Zebra", b = "antylopa";
cout << (a < b) << "\n"; // Z (90) < a (97)
string x = a, y = b; // kopie do porównania
for (char &c : x) c = tolower(c);
for (char &c : y) c = tolower(c);
cout << (x < y) << "\n"; // zebra > antylopa
cout << a << " " << b << "\n"; // oryginały bez zmian
Gdy w zadaniu kolejność ma być „prawdziwie alfabetyczna”, bez względu na wielkość liter, porównuj kopie zamienione na małe litery. Oryginały zostają nietknięte, więc możesz je potem wypisać tak, jak je wczytałeś.
W większości zadań olimpijskich ten problem nie występuje, bo słowa składają się z samych małych liter. Ale gdy dane mieszają wielkość liter — na przykład nazwiska z wielkiej litery — pamiętaj o tej pułapce.
Liczby zapisane jako napisy
Druga niespodzianka. Jako napisy "10" < "9" — bo porównanie zaczyna się od pierwszych znaków, a 1 jest przed 9. Napis nie wie, że zawiera liczbę! Kiedy to ważne? Gdy liczby są tak wielkie, że nie mieszczą się w żadnym typie i muszą zostać napisami — zajmiemy się nimi w części 7. Na szczęście naprawa jest prosta. Dla liczb nieujemnych bez zer na początku: dłuższa liczba jest większa, a gdy długości są równe — porównanie napisów daje właściwy wynik, bo cyfry stoją w tabeli ASCII po kolei.
string a, b;
cin >> a >> b;
cout << (a < b) << "\n"; // porównanie napisów — uwaga!
bool aMniejsza;
if (a.length() != b.length()) {
aMniejsza = a.length() < b.length();
} else {
aMniejsza = a < b;
}
cout << aMniejsza << "\n"; // porównanie liczb
Jako napisy „99” jest większe od „100”, bo 9 > 1 na pierwszej pozycji — stąd 0 w pierwszym wierszu. Jako liczby 99 < 100: krótsza liczba jest mniejsza.
Przy równych długościach zwykłe porównanie napisów działa: „123” < „129”, bo pierwsza różnica (3 i 9) rozstrzyga tak samo jak przy liczbach.
Najmniejszy i największy napis
Skoro napisy umieją się porównywać, możesz szukać wśród nich minimum i maksimum — dokładnie tym samym schematem co w tablicach. Startujesz od pierwszego napisu, a nie od pustego: pusty byłby mniejszy od wszystkich i nigdy by nie przegrał w szukaniu minimum.
int n;
cin >> n;
string s, najm, najw;
cin >> s;
najm = s;
najw = s;
for (int i = 1; i < n; i++) {
cin >> s;
if (s < najm) najm = s;
if (s > najw) najw = s;
}
cout << najm << " " << najw << "\n";
Pierwsze słowo — „gruszka” — od razu zostaje i minimum, i maksimum. Potem każde kolejne słowo porównujemy z rekordami: „jablko” jest dalej niż „gruszka” (j > g), więc zostaje maksimum; „banan” jest wcześniej niż wszystko dotąd, więc zostaje minimum; i tak dalej.
Pętla zaczyna się od i = 1, bo jedno słowo wczytaliśmy przed nią. Słów jest n, więc w pętli wczytujemy n − 1 pozostałych.
Zamiana i porządkowanie: swap
swap(a, b) działa także na napisach — zamienia całą ich zawartość. Dzięki temu możesz uporządkować kilka słów alfabetycznie dokładnie tym sposobem, którym w lekcji o if porządkowałeś trzy liczby: trzy porównania i trzy ewentualne zamiany.
string a, b, c;
cin >> a >> b >> c;
if (a > b) swap(a, b); // teraz a <= b
if (b > c) swap(b, c); // największe trafia do c
if (a > b) swap(a, b); // porządek w pierwszej parze
cout << a << " " << b << " " << c << "\n";
| krok | a | b | c |
|---|---|---|---|
| start | ola | ania | ewa |
a > b — zamiana | ania | ola | ewa |
b > c — zamiana | ania | ewa | ola |
a > b — bez zmian | ania | ewa | ola |
Dla wielu słów takie ręczne zamiany przestają wystarczać. Sortowanie dowolnie wielu napisów jednym poleceniem poznasz w lekcji o sortowaniu — a działa ono na napisach dokładnie według kolejności słownikowej z tej części.
Porównanie ręczne: wspólny początek
Czasem nie wystarczy wiedzieć, który napis jest mniejszy — trzeba wiedzieć, gdzie się różnią. Wtedy piszesz porównanie sam: idziesz od początku, dopóki znaki są takie same i żaden napis się nie skończył. Pozycja, na której się zatrzymasz, to długość wspólnego początku.
string a, b;
cin >> a >> b;
int na = a.length(), nb = b.length();
int i = 0;
while (i < na && i < nb && a[i] == b[i]) {
i++;
}
cout << "wspolny poczatek: " << i << " znaki\n";
if (i < na && i < nb) {
cout << "roznica: " << a[i] << " i " << b[i] << "\n";
}
Kolejność warunków w while znów ma znaczenie: najpierw sprawdzamy, czy i mieści się w obu napisach, a dopiero potem porównujemy a[i] z b[i]. Skrócone obliczanie chroni przed zajrzeniem poza krótszy napis.
Po pętli są trzy możliwości: znaleźliśmy różnicę (wtedy oba warunki i < … są prawdziwe), skończył się krótszy napis albo napisy są identyczne. To dokładnie te trzy przypadki, które rozważa operator <.
Najpierw odpowiedz w myślach — rozpisz sobie znaki napisu w pudełkach z numerami i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.
string a = "abc";
cout << (a < "abd") << (a < "ab");
Pokaż odpowiedź
string a = "Ala", b = "ala";
cout << (a < b);
Pokaż odpowiedź
string a = "9", b = "10";
cout << (a < b);
Pokaż odpowiedź
string a = "kot", b = "kotek";
cout << (a < b) << (a > b) << (a == b);
Pokaż odpowiedź
string a = "b", b = "aaa";
cout << (a > b);
Pokaż odpowiedź
string a = "zebra", b = "Zebra";
cout << (a == b) << (a > b);
Pokaż odpowiedź
string t[3] = {"ma", "ala", "kota"};
string m = t[0];
for (int i = 1; i < 3; i++) {
if (t[i] < m) m = t[i];
}
cout << m;
Pokaż odpowiedź
string a = " a", b = "a";
cout << (a < b);
Pokaż odpowiedź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
Fragmenty i szukanie: substr, find, erase, insert, replace
Do tej pory wszystko robiłeś pętlą, znak po znaku. To dobra szkoła, ale napis ma też gotowe metody — polecenia pisane po kropce, jak s.length() — które załatwiają typowe zadania jedną linijką. W tej części poznasz pięć najważniejszych: substr wycina kawałek, find szuka fragmentu, a erase, insert i replace usuwają, wstawiają i podmieniają. Każdą pokażemy na rysunku pudełek, żeby było widać, które dokładnie znaki biorą udział.
substr — kawałek napisu
s.substr(od, ile) tworzy nowy napis z ile znaków napisu s, zaczynając od pozycji od. Nazwa to skrót od „substring” — podnapis, kawałek napisu. Sam napis s się nie zmienia.
string s = "programowanie";
cout << s.substr(3, 4) << "\n"; // od 3, cztery znaki
cout << s.substr(0, 7) << "\n"; // od początku, siedem znaków
cout << s.substr(7) << "\n"; // bez drugiej liczby: do końca
cout << s.substr(10, 100) << "\n"; // za dużo? bierze do końca
cout << s << "\n"; // s bez zmian
substr: traktowanie drugiej liczby jak pozycji końca. s.substr(3, 6) to sześć znaków od pozycji 3, a nie znaki od 3 do 6. Gdy chcesz fragment od pozycji a do pozycji b włącznie, policz jego długość: s.substr(a, b - a + 1).
Jeśli poprosisz o więcej znaków, niż zostało do końca, substr się nie obrazi — po prostu weźmie wszystko do końca. Tak było z s.substr(10, 100).
Gdy początek wypada za napisem
Pierwsza liczba musi wskazywać miejsce w napisie albo tuż za nim. s.substr(s.length()) jest jeszcze w porządku — daje pusty napis, bo za ostatnim znakiem nic już nie ma. Ale s.substr(s.length() + 1) i dalsze to błąd: program zatrzyma się z komunikatem out_of_range, tak jak przy at.
string s = "kot";
cout << "[" << s.substr(3) << "]\n"; // od pozycji 3 = tuż za napisem
cout << "[" << s.substr(1, 0) << "]\n"; // zero znaków — też pusty
string s = "kot";
cout << s.substr(4) << "\n"; // BŁĄD: 4 > długość 3
Początek i koniec napisu
Dwa najczęstsze kawałki to początek (przedrostek) i koniec (przyrostek). Początek z k znaków to s.substr(0, k). Koniec z k znaków zaczyna się na pozycji n - k, więc to s.substr(n - k). Dzięki nim łatwo sprawdzisz, czy słowo zaczyna się albo kończy na coś.
string s = "kotlet";
int n = s.length();
cout << s.substr(0, 3) << "\n"; // pierwsze 3 znaki
cout << s.substr(n - 3) << "\n"; // ostatnie 3 znaki
if (s.substr(0, 3) == "kot") {
cout << "zaczyna sie od kot\n";
}
if (n >= 3 && s.substr(n - 3) == "let") {
cout << "konczy sie na let\n";
}
Po co warunek n >= 3? Dla słowa krótszego niż 3 znaki n - 3 jest ujemne. Liczba ujemna przekazana do substr zamienia się w ogromną liczbę bez znaku (pamiętasz pułapkę z części 1?) i program się wysypie. Skrócone obliczanie sprawia, że dla krótkich słów substr w ogóle się nie wykona.
s.substr(0, 3) jest bezpieczne nawet dla krótszych słów — weźmie tyle, ile jest.
find — gdzie jest fragment?
s.find(x) szuka w napisie s fragmentu x i zwraca pozycję jego pierwszego znaku przy pierwszym wystąpieniu. Szukać możesz całego napisu albo jednego znaku. To dokładnie ta pętla, którą pisałeś w części 3, tylko gotowa.
string s = "ala ma kota a kot ma ale";
cout << s.find("kot") << "\n"; // pierwsze wystąpienie
cout << s.find('m') << "\n"; // można szukać znaku
cout << s.find("ma") << "\n";
cout << s.find("kot", 8) << "\n"; // szukaj od pozycji 8
cout << s.rfind("ma") << "\n"; // szukaj od końca
Druga liczba w find mówi, od której pozycji zacząć szukanie. s.find("kot", 8) pomija wszystko przed pozycją 8, więc pierwsze „kot” (od 7) już się nie liczy i wychodzi 14.
rfind („reverse find”) szuka od końca, czyli zwraca ostatnie wystąpienie. Uwaga: pozycja nadal liczy się od początku napisu — rfind zmienia tylko kierunek szukania.
Gdy nie ma: string::npos
Co zwraca find, gdy niczego nie znajdzie? Specjalną wartość string::npos — „no position”, brak pozycji. To największa liczba typu długości, czyli ta sama ogromna liczba, którą widziałeś w części 1 jako 0 − 1. Bezpiecznie jest zawsze porównywać wynik find właśnie z string::npos.
string s = "programowanie";
if (s.find("gram") != string::npos) {
cout << "jest gram na pozycji " << s.find("gram") << "\n";
}
if (s.find("kot") == string::npos) {
cout << "nie ma kota\n";
}
cout << s.find("kot") << "\n"; // npos wypisany wprost
int p = s.find("kot");
cout << p << "\n"; // npos włożony do int
Dwie ostatnie linijki pokazują ciekawostkę, z której korzysta wielu zawodników. Gdy wynik find zapiszesz w zwykłej zmiennej int, wartość npos zamienia się w −1. Dzięki temu możesz pisać tak samo jak przy szukaniu w tablicy: int p = s.find(x); i potem if (p == -1).
Oba sposoby są dobre — wybierz jeden i trzymaj się go. W tej lekcji przy pętlach będziemy używać int i −1, bo są krótsze i znajome z tablic.
string s = "kotlet";
if (s.find("kot")) { // ŹLE!
cout << "jest\n";
} else {
cout << "nie ma\n";
}
find zwraca 0 — a 0 w warunku to fałsz. Program mówi „nie ma”, choć jest. Z kolei gdy fragmentu naprawdę nie ma, npos to liczba różna od zera, czyli prawda. Taki warunek działa dokładnie na odwrót, niż chcesz. Zawsze pisz pełne porównanie: s.find(x) != string::npos albo p != -1.
Wszystkie wystąpienia
Żeby znaleźć wszystkie wystąpienia, wołasz find w pętli. Każde kolejne szukanie zaczynasz za poprzednim znaleziskiem. Tylko: jak daleko za? Są dwie możliwości i dają różne wyniki.
string s = "abrakadabra";
int p = s.find("abra");
while (p != -1) {
cout << p << " ";
p = s.find("abra", p + 1); // szukaj dalej, od następnej pozycji
}
cout << "\n";
string s = "aaaa", x = "aa";
int k1 = 0, k2 = 0;
int p = s.find(x);
while (p != -1) {
k1++;
p = s.find(x, p + 1); // mogą na siebie nachodzić
}
p = s.find(x);
while (p != -1) {
k2++;
p = s.find(x, p + x.length()); // bez nachodzenia
}
cout << k1 << " " << k2 << "\n";
W napisie „aaaa” fragment „aa” zaczyna się na pozycjach 0, 1 i 2 — trzy wystąpienia, które na siebie nachodzą. Jeśli każde kolejne szukanie zaczynasz od p + 1, znajdziesz wszystkie trzy. Jeśli od p + x.length() — przeskakujesz całe znalezisko i znajdziesz tylko te, które się nie nakładają: 0 i 2. Które liczenie jest właściwe, zależy od zadania — zawsze przeczytaj dokładnie, o co pyta.
Rozcinanie napisu w miejscu znaku
find i substr razem pozwalają rozciąć napis w wybranym miejscu: find mówi, gdzie stoi znak podziału, a substr wycina kawałki przed nim i za nim. To trzeci — po getline z przecinkiem i pętli z części 2 — sposób na dzielenie tekstu.
string email = "jan.kowalski@szkola.edu.pl";
int p = email.find('@');
string uzytkownik = email.substr(0, p); // p znaków przed @
string domena = email.substr(p + 1); // wszystko za @
cout << uzytkownik << "\n" << domena << "\n";
string plik = "zdjecie.wakacje.jpg";
int p = plik.rfind('.'); // ostatnia kropka
cout << plik.substr(p + 1) << "\n"; // rozszerzenie
cout << plik.substr(0, p) << "\n"; // nazwa bez rozszerzenia
Zwróć uwagę na email.substr(0, p). Znak @ stoi na pozycji p, a przed nim jest dokładnie p znaków (pozycje od 0 do p − 1) — dlatego długość kawałka to p. A w nazwie pliku szukamy kropki od końca, bo kropek może być kilka, a rozszerzenie to tylko to, co za ostatnią.
Gdy kawałki mają stałe miejsca — jak godzina w postaci 07:45 — nie trzeba nawet szukać. Wystarczy substr i znana z lekcji o typach funkcja stoi, która zamienia napis na liczbę:
string czas;
cin >> czas; // np. 07:45
int g = stoi(czas.substr(0, 2)); // "07" → 7
int m = stoi(czas.substr(3, 2)); // "45" → 45
cout << g * 60 + m << "\n"; // minuty od północy
erase i insert — usuwanie i wstawianie
Teraz metody, które zmieniają napis. s.erase(od, ile) usuwa ile znaków od pozycji od — znaki za nimi przesuwają się w lewo i zajmują wolne miejsce. s.insert(od, t) wstawia napis t tak, że jego pierwszy znak stanie na pozycji od — znaki od tej pozycji przesuwają się w prawo.
string s = "programowanie";
s.erase(7, 3); // usuń 3 znaki od pozycji 7
cout << s << "\n";
s.insert(0, "super"); // wstaw na początek
cout << s << "\n";
s.insert(s.length(), "!"); // wstaw na sam koniec
cout << s << "\n";
s.erase(0, 5); // usuń 5 pierwszych znaków
cout << s << "\n";
s.erase(7); // bez drugiej liczby: do końca
cout << s << "\n";
| po linijce | s |
|---|---|
s.erase(7, 3); | programnie |
s.insert(0, "super"); | superprogramnie |
s.insert(s.length(), "!"); | superprogramnie! |
s.erase(0, 5); | programnie! |
s.erase(7); | program |
W odróżnieniu od substr te metody zmieniają s na stałe — nie trzeba niczego przypisywać. Wstawianie na pozycję s.length() to to samo co s += ….
replace — podmiana fragmentu
s.replace(od, ile, t) to erase i insert w jednym: usuwa ile znaków od pozycji od i w ich miejsce wstawia napis t. Nowy kawałek może być krótszy albo dłuższy od usuniętego — reszta napisu sama się przesunie.
string s = "Ala ma kota";
s.replace(7, 4, "psa"); // od pozycji 7 zamień 4 znaki na "psa"
cout << s << "\n";
s.replace(0, 3, "Ola i Ela");
cout << s << "\n";
string s = "kot i kot i kotek";
string co = "kot", na = "pies";
int p = s.find(co);
while (p != -1) {
s.replace(p, co.length(), na);
p = s.find(co, p + na.length()); // szukaj ZA wstawionym tekstem
}
cout << s << "\n";
Prawy program zamienia wszystkie wystąpienia. Najważniejszy jest ostatni wiersz pętli: kolejne szukanie zaczyna się za właśnie wstawionym tekstem, czyli od p + na.length(). Gdyby zaczynało się od p, a nowy tekst zawierał stary (na przykład zamieniasz „a” na „aa”), program znajdowałby w kółko to, co sam przed chwilą wstawił — i nigdy by się nie skończył.
| metoda | co robi | zmienia s? |
|---|---|---|
s.substr(od, ile) | zwraca kawałek: ile znaków od pozycji od (bez ile — do końca) | nie |
s.find(x), s.find(x, od) | pozycja pierwszego wystąpienia x (szukając od pozycji od) albo npos | nie |
s.rfind(x) | pozycja ostatniego wystąpienia x albo npos | nie |
s.erase(od, ile) | usuwa ile znaków od pozycji od (bez ile — do końca) | tak |
s.insert(od, t) | wstawia napis t przed pozycję od | tak |
s.replace(od, ile, t) | zamienia ile znaków od pozycji od na napis t | tak |
Najpierw odpowiedz w myślach — rozpisz sobie znaki napisu w pudełkach z numerami i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.
string s = "informatyka";
cout << s.substr(2, 5);
Pokaż odpowiedź
string s = "informatyka";
cout << s.substr(7);
Pokaż odpowiedź
substr bierze wszystko od pozycji 7 do końca.string s = "banan";
cout << s.find("an") << " " << s.rfind("an");
Pokaż odpowiedź
find daje pierwsze wystąpienie, rfind — ostatnie.string s = "banan";
cout << s.find("an", 2);
Pokaż odpowiedź
string s = "kot";
int p = s.find("pies");
cout << p;
Pokaż odpowiedź
find zwraca npos, a npos zapisany w int to −1.string s = "abcdef";
s.erase(1, 2);
cout << s;
Pokaż odpowiedź
string s = "abc";
s.insert(1, "XY");
cout << s << s.length();
Pokaż odpowiedź
string s = "mama";
int k = 0, p = s.find("ma");
while (p != -1) {
k++;
p = s.find("ma", p + 1);
}
cout << k;
Pokaż odpowiedź
string s = "12:30";
cout << stoi(s.substr(0, 2)) + stoi(s.substr(3));
Pokaż odpowiedź
stoi("12") to liczba 12, a stoi("30") — 30. Teraz plus to dodawanie liczb: 42.9 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
Napisy i liczby: cyfry, zamiany i olbrzymy
Liczba i napis z cyframi to dla komputera dwie zupełnie różne rzeczy. 123 to liczba — można ją dodawać i mnożyć. "123" to trzy znaki w pudełkach — można je wycinać, odwracać i liczyć. W tej części nauczysz się przechodzić między tymi światami i korzystać z obu. A na koniec zobaczysz, jak liczyć na liczbach, które mają sto albo tysiąc cyfr — za dużych dla każdego typu, ale nie dla napisu.
Cyfra jako znak, cyfra jako liczba
Przypomnienie z lekcji o typach: znaki cyfr stoją w tabeli ASCII po kolei, od '0' (kod 48) do '9' (kod 57). Dlatego c - '0' zamienia znak cyfry na jej wartość, a '0' + d zamienia wartość od 0 do 9 na znak. Te dwa zapisy będą Ci towarzyszyć przez całą tę część.
char c = '7';
int d = c - '0'; // znak '7' → liczba 7
char e = '0' + 3; // liczba 3 → znak '3'
cout << d * 2 << " " << e << "\n";
string s = "2026";
int suma = 0;
for (char z : s) {
suma += z - '0'; // dodajemy wartości cyfr
}
cout << suma << "\n";
| zapis | wynik | typ |
|---|---|---|
'7' | znak 7 (kod 55) | char |
'7' - '0' | 7 | int |
'0' + 3 | 51 | int |
(char)('0' + 3) | znak 3 | char |
'0' + 3 to liczba 51 — kod znaku 3. Żeby była znakiem, trzeba ją zapisać do zmiennej char (jak e w programie) albo zrzutować przez (char).
to_string i stoi — w obie strony
Całą liczbę zamienisz na napis funkcją to_string(x), a napis z cyframi na liczbę — funkcją stoi(s) („string to int”). Dla dużych liczb jest stoll („string to long long”). Obie znasz z lekcji o typach. Teraz zobacz, ile dają w połączeniu z tym, co wiesz o napisach: liczba cyfr to po prostu długość napisu, a pierwsza i ostatnia cyfra to pierwszy i ostatni znak.
int x = 4096;
string s = to_string(x); // "4096"
cout << s.length() << "\n"; // liczba cyfr
cout << s[0] << s[s.length() - 1] << "\n"; // pierwsza i ostatnia cyfra
string t = "123";
cout << stoi(t) + 1 << "\n"; // liczba: dodawanie
cout << t + "1" << "\n"; // napis: sklejanie
long long duza = stoll("9000000000");
cout << duza * 2 << "\n";
long long n;
cin >> n;
string s = to_string(n), w = "";
int k = s.length();
for (int i = k - 1; i >= 0; i--) {
w += s[i];
}
if (s == w) {
cout << "TAK\n";
} else {
cout << "NIE\n";
}
W lekcji o pętli while sprawdzałeś, czy liczba jest palindromem, rozbierając ją na cyfry przez % 10 i / 10. Z napisem jest krócej: zamieniasz liczbę na napis i porównujesz go z odwróconym. Oba sposoby są dobre — wybierz ten, który w danym zadaniu jest prostszy.
stoi czyta cyfry od początku napisu i zatrzymuje się na pierwszym znaku, który do liczby nie pasuje: stoi("12abc") to 12, a stoi(" 7") to 7 (spacje na początku pomija). Ale gdy napis nie zaczyna się od liczby — stoi("abc") — program zatrzyma się z błędem invalid_argument. A gdy liczba nie mieści się w int — z błędem out_of_range; wtedy użyj stoll.
Olbrzymy: liczby za duże dla każdego typu
Największy typ, który znasz, long long, mieści liczby do około 9 · 1018 — to 19 cyfr. Co zrobić z liczbą, która ma 100 cyfr? W zadaniach olimpijskich takie liczby się zdarzają, a jedyne miejsce, gdzie się zmieszczą, to napis. Wczytujesz je przez cin >> s jak zwykłe słowo i liczysz na nich cyfra po cyfrze — tak jak w szkole liczysz pisemnie.
Sporo pytań o olbrzyma da się rozstrzygnąć bez żadnych obliczeń, samym oglądaniem cyfr. Ostatnia cyfra mówi o parzystości i o podzielności przez 5 i 10. Suma cyfr — o podzielności przez 3 i 9. Dwie ostatnie cyfry — o podzielności przez 4.
string s;
cin >> s;
int n = s.length();
int ostatnia = s[n - 1] - '0';
int suma = 0;
for (char c : s) {
suma += c - '0';
}
cout << "cyfr: " << n << "\n";
cout << "parzysta: " << (ostatnia % 2 == 0) << "\n";
cout << "podzielna przez 3: " << (suma % 3 == 0) << "\n";
Ta liczba ma 29 cyfr — o dziesięć za dużo dla long long. Ostatnia cyfra to 9, więc liczba jest nieparzysta. Suma cyfr to 135, a 135 dzieli się przez 3 — więc cała liczba też.
Zwróć uwagę, że suma cyfr jest mała nawet dla gigantycznej liczby: tysiąc cyfr daje sumę najwyżej 9000. Spokojnie zmieści się w int.
Reszta z dzielenia olbrzyma
A co z podzielnością przez 7 albo przez 1000? Tu przydaje się sztuczka z lekcji o modulo. Liczbę budujemy cyfra po cyfrze: przy każdej nowej cyfrze stara wartość mnoży się przez 10 i dochodzi cyfra. Ale nie musimy pamiętać całej wartości — wystarczy jej reszta. Po każdym kroku bierzemy % k, więc liczby nigdy nie urosną.
string s;
long long k;
cin >> s >> k;
long long r = 0;
for (char c : s) {
r = (r * 10 + (c - '0')) % k;
}
cout << r << "\n";
| cyfra | r · 10 + cyfra | r = … % 7 |
|---|---|---|
| 1 | 0 · 10 + 1 = 1 | 1 |
| 2 | 1 · 10 + 2 = 12 | 5 |
| 3 | 5 · 10 + 3 = 53 | 4 |
| 4 | 4 · 10 + 4 = 44 | 2 |
| … | … | … |
Po pierwszych czterech cyfrach r = 2 — i rzeczywiście 1234 = 7 · 176 + 2. Na końcu zostaje reszta z całej liczby. r nigdy nie przekracza k, a r * 10 + 9 mieści się w long long nawet dla k rzędu miliarda.
Dodawanie pisemne na napisach
Dwóch olbrzymów można dodać dokładnie tak, jak uczyli Cię w podstawówce: od ostatnich cyfr, z przeniesieniem. Idziemy dwoma indeksami od końca obu liczb. W każdym kroku dodajemy dwie cyfry (albo jedną, gdy krótsza liczba już się skończyła) i przeniesienie z poprzedniego kroku. Ostatnia cyfra sumy trafia do wyniku, a dziesiątki idą dalej jako przeniesienie.
string a, b;
cin >> a >> b;
string wynik = "";
int i = a.length() - 1, j = b.length() - 1;
int przeniesienie = 0;
while (i >= 0 || j >= 0 || przeniesienie > 0) {
int suma = przeniesienie;
if (i >= 0) {
suma += a[i] - '0';
i--;
}
if (j >= 0) {
suma += b[j] - '0';
j--;
}
wynik = (char)('0' + suma % 10) + wynik; // cyfra na początek
przeniesienie = suma / 10;
}
cout << wynik << "\n";
| krok | cyfry | suma | do wyniku | dalej | wynik |
|---|---|---|---|---|---|
| 1. | 9 + 4 | 13 | 3 | 1 | 3 |
| 2. | 9 + 3 + 1 | 13 | 3 | 1 | 33 |
| 3. | 9 + 2 + 1 | 12 | 2 | 1 | 233 |
| 4. | — + 1 + 1 | 2 | 2 | 0 | 2233 |
Warunek pętli ma trzy części: działamy, dopóki zostały cyfry w a, albo w b, albo jest jeszcze przeniesienie. Bez trzeciej części przy 999 + 1 zgubilibyśmy jedynkę na początku wyniku.
Nowe cyfry wyniku dochodzą od końca, więc doklejamy je z przodu. Przy tysiącach cyfr to w zupełności wystarczy.
System dwójkowy na napisach
W lekcji o modulo zamieniałeś liczby na inne systemy. Napisy bardzo to ułatwiają, bo liczba w systemie dwójkowym to po prostu napis z zer i jedynek. W stronę „napis → liczba” działa ten sam trik co przy reszcie z olbrzyma, tylko mnożymy przez 2 zamiast przez 10. W stronę „liczba → napis” zbieramy reszty z dzielenia przez 2 i doklejamy je z przodu, bo wychodzą od końca.
string b;
cin >> b;
long long w = 0;
for (char c : b) {
w = w * 2 + (c - '0');
}
cout << w << "\n";
long long n;
cin >> n;
string b = "";
if (n == 0) {
b = "0";
}
while (n > 0) {
b = (char)('0' + n % 2) + b;
n /= 2;
}
cout << b << "\n";
Prześledź lewy program dla 101101: w = 1, potem 1 · 2 + 0 = 2, 2 · 2 + 1 = 5, 5 · 2 + 1 = 11, 11 · 2 + 0 = 22, 22 · 2 + 1 = 45. Każda kolejna cyfra przesuwa dotychczasową wartość o jedno miejsce w lewo (mnożenie przez 2) i dokłada się na końcu. Zero obsługujemy osobno w prawym programie, bo dla n = 0 pętla nie wykona się ani razu i napis zostałby pusty.
Liczby ukryte w tekście
Ostatni schemat tej części: tekst, w którym między literami stoją liczby, na przykład „W koszyku 12 jablek i 125 sliwek”. Jak wyciągnąć z niego liczby? Idziemy znak po znaku i budujemy bieżącą liczbę: każda cyfra to liczba = liczba * 10 + cyfra. Gdy trafimy na znak, który nie jest cyfrą, bieżąca liczba się skończyła — zapisujemy ją i zaczynamy od zera.
string s;
getline(cin, s);
long long suma = 0, liczba = 0;
for (char c : s) {
if (isdigit(c)) {
liczba = liczba * 10 + (c - '0');
} else {
suma += liczba; // liczba się skończyła
liczba = 0;
}
}
suma += liczba; // liczba na samym końcu tekstu
cout << suma << "\n";
Dodawanie przy każdym znaku, który nie jest cyfrą, wygląda podejrzanie — przecież liter jest dużo. Ale gdy przed literą nie było cyfr, liczba wynosi 0, więc dodanie jej niczego nie zmienia. Prosto i bez dodatkowych warunków.
Najczęstszy błąd: brak linijki po pętli. Gdy tekst kończy się cyfrą, ostatnia liczba nie ma za sobą litery, która by ją „zamknęła” — trzeba ją dodać osobno.
Najpierw odpowiedz w myślach — rozpisz sobie znaki napisu w pudełkach z numerami i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.
cout << '8' - '0' + 1;
Pokaż odpowiedź
'8' - '0' to wartość cyfry, 8. Plus 1 daje 9.cout << (char)('0' + 5) << 5;
Pokaż odpowiedź
string s = to_string(305);
cout << s.length() << s[1];
Pokaż odpowiedź
string a = "40", b = "2";
cout << stoi(a) + stoi(b) << " " << a + b;
Pokaż odpowiedź
string b = "1101";
int w = 0;
for (char c : b) {
w = w * 2 + (c - '0');
}
cout << w;
Pokaż odpowiedź
int n = 6;
string b = "";
while (n > 0) {
b = (char)('0' + n % 2) + b;
n /= 2;
}
cout << b;
Pokaż odpowiedź
cout << stoi("12abc") + 1;
Pokaż odpowiedź
stoi czyta cyfry od początku i zatrzymuje się na literze a: wychodzi 12. Plus 1 daje 13.string s = "987";
int r = 0;
for (char c : s) {
r = (r * 10 + (c - '0')) % 4;
}
cout << r;
Pokaż odpowiedź
9 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
Napisy na olimpiadzie: liczniki, szyfry, okna
Na olimpiadzie napisy są długie — sto tysięcy, a nawet milion znaków — a pytań o nie jest dużo. Pętla w pętli, która dla zwykłych danych działa w mgnieniu oka, nagle potrzebuje godzin. W tej części poznasz sztuczki, które pozwalają odpowiadać szybko: tablicę liczników liter, szyfry z modulo, przesuwane okno i sumy prefiksowe na napisie. Większość z nich znasz już z tablic — teraz zobaczysz je w świecie tekstu. Na koniec sprawdzimy, które operacje na napisach są tanie, a które drogie.
Tablica liczników liter
W lekcji o tablicach liczyłeś litery w tablicy int ile[26], gdzie literze c odpowiada pudełko c - 'a'. To jedna z najważniejszych sztuczek w zadaniach tekstowych, bo wiele pytań dotyczy nie kolejności liter, tylko tego, ile ich jest. Na przykład: dwa słowa są anagramami (jedno powstaje z drugiego przez przestawienie liter), gdy każda litera występuje w nich tyle samo razy.
string a, b;
cin >> a >> b;
int ile[26] = {};
for (char c : a) ile[c - 'a']++; // litery a dodajemy
for (char c : b) ile[c - 'a']--; // litery b odejmujemy
bool anagram = true;
for (int k = 0; k < 26; k++) {
if (ile[k] != 0) anagram = false;
}
cout << (anagram ? "TAK" : "NIE") << "\n";
Zamiast dwóch tablic liczników wystarczy jedna: litery pierwszego słowa zwiększają liczniki, a drugiego — zmniejszają. Jeśli słowa mają te same litery w tych samych ilościach, wszystko się zeruje.
Ile to kosztuje? Jedno przejście po każdym słowie i 26 obrotów na koniec. Porównywanie „każda litera z każdą” byłoby dużo wolniejsze — dla słów o stu tysiącach liter różnica to ułamek sekundy kontra wiele minut.
Gdy w tekście mogą być nie tylko małe litery, możesz liczyć wszystkie znaki naraz. Kody ASCII zwykłych znaków mieszczą się między 0 a 127, więc wystarczy tablica int ile[128], a znak sam w sobie jest numerem pudełka: ile[c]++.
string s = "programowanie";
int ile[128] = {};
for (char c : s) {
ile[c]++; // znak to numer pudełka
}
for (int c = 0; c < 128; c++) {
if (ile[c] > 1) {
cout << (char)c << " "; // znaki, które się powtarzają
}
}
cout << "\n";
Druga pętla przechodzi po wszystkich kodach od 0 do 127 i wypisuje znaki, które wystąpiły więcej niż raz. Dzięki temu wynik jest od razu uporządkowany według tabeli ASCII — w przypadku małych liter to po prostu kolejność alfabetyczna.
W „programowanie” litery a, o i r występują po dwa razy, a wszystkie pozostałe — po razie.
Szyfry i modulo
Szyfr Cezara znasz z wcześniejszych lekcji: każdą literę przesuwamy o k miejsc w alfabecie, a gdy wyjdziemy za z — wracamy na początek. To „wracanie w kółko” to dokładnie modulo: numer litery to c - 'a', po przesunięciu (c - 'a' + k) % 26, a z powrotem na znak — 'a' + …. Wielkie litery obsługujemy osobno, z 'A' zamiast 'a', a pozostałe znaki zostawiamy.
int k;
string s;
cin >> k;
cin.ignore();
getline(cin, s);
for (char &c : s) {
if (islower(c)) {
c = 'a' + (c - 'a' + k) % 26;
} else if (isupper(c)) {
c = 'A' + (c - 'A' + k) % 26;
}
}
cout << s << "\n";
Z przesuwa się o 3 na C: numer 25, plus 3 to 28, a 28 % 26 = 2, czyli C. Spacje zostają na miejscu, bo nie są literami.
Jak odszyfrować? Przesunąć o k wstecz. Odejmowanie przy modulo bywa zdradliwe (pamiętasz ujemne reszty z lekcji o modulo?), więc zamiast odejmować k, dodaj 26 - k — przesunięcie o 26 to pełne okrążenie, które niczego nie zmienia.
W ćwiczeniach poznasz silniejszy szyfr Vigenère’a, w którym każda litera przesuwa się o inną wartość — i tam modulo przyda się dwa razy.
Okno o stałej długości
Typowe pytanie: który fragment długości k zawiera najwięcej samogłosek? Fragmentów jest n − k + 1, a każdy ma k znaków. Liczenie każdego od nowa to około n · k operacji — dla n = 100 000 i k = 50 000 to miliardy. A przecież sąsiednie fragmenty różnią się tylko dwoma znakami! Wyobraź sobie okno o szerokości k, które przesuwamy po napisie o jedno miejsce: z lewej jeden znak wypada, z prawej jeden wchodzi. Wystarczy poprawić licznik o te dwa znaki.
string s, sam = "aeiouy";
int k;
cin >> s >> k;
int n = s.length();
int ile = 0;
for (int i = 0; i < k; i++) { // pierwsze okno: 0..k-1
if (sam.find(s[i]) != string::npos) ile++;
}
int najlepiej = ile;
for (int i = k; i < n; i++) { // okno przesuwa się o 1
if (sam.find(s[i]) != string::npos) ile++; // wchodzi s[i]
if (sam.find(s[i - k]) != string::npos) ile--; // wypada s[i - k]
if (ile > najlepiej) najlepiej = ile;
}
cout << najlepiej << "\n";
Zwróć uwagę na trik z sam.find(s[i]). Zamiast długiego warunku c == 'a' || c == 'e' || … szukamy znaku w napisie z samogłoskami — jeśli find go znajdzie, to samogłoska. Krótko i bez literówek.
Pierwsza pętla liczy pierwsze okno. Druga przesuwa okno: gdy jego prawy koniec jest na pozycji i, lewy jest na i - k + 1, więc znak, który właśnie wypadł, stał na i - k. Całość to około n kroków zamiast n · k. Najlepsze okno to „anie” na końcu — trzy samogłoski.
Sumy prefiksowe na napisie
A gdy pytań jest dużo i każde dotyczy innego fragmentu — „ile liter a jest między pozycją l a r?” — pomagają sumy prefiksowe z lekcji o tablicach. p[i] to liczba liter a wśród pierwszych i znaków napisu. Fragment od l-tego do r-tego znaku (licząc od 1) zawiera wtedy p[r] - p[l - 1] liter a — jedno odejmowanie zamiast pętli.
string s;
cin >> s;
int n = s.length();
int p[1001];
p[0] = 0;
for (int i = 1; i <= n; i++) {
p[i] = p[i - 1] + (s[i - 1] == 'a'); // i-ty znak to s[i - 1]
}
int q;
cin >> q;
for (int k = 0; k < q; k++) {
int l, r;
cin >> l >> r;
cout << p[r] - p[l - 1] << "\n";
}
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| znak | — | a | b | r | a | c | a | d | a | b | r | a |
| p[i] | 0 | 1 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 4 | 4 | 5 |
Zapis (s[i - 1] == 'a') to porównanie, które daje true albo false — a w rachunkach true liczy się jako 1, a false jako 0. Dzięki temu dodajemy jedynkę dokładnie wtedy, gdy znak to a.
Pytanie „4 8”: p[8] - p[3] = 4 − 1 = 3. Znaki od 4. do 8. to a, c, a, d, a — trzy litery a.
Które operacje są szybkie, a które wolne?
Na olimpiadzie program ma limit czasu, zwykle około sekundy — w tym czasie komputer wykona kilkaset milionów prostych operacji. Dlatego warto wiedzieć, ile kosztują operacje na napisach. Niektóre zajmują chwilę bez względu na długość napisu. Inne muszą przejść po wszystkich znakach — i jeśli robisz je w pętli, koszt mnoży się przez liczbę obrotów.
| operacja | koszt | uwagi |
|---|---|---|
s[i], s.length(), s.empty() | stały | zawsze błyskawicznie |
s += c, s.push_back(c), s.pop_back() | stały | dokładanie i zabieranie na końcu |
s + t, s.substr(od, ile), string t = s | długość wyniku | powstaje nowy napis — każdy znak trzeba skopiować |
s == t, s < t | do pierwszej różnicy | dla prawie równych napisów — cała długość |
c + s, s.insert(0, …), s.erase(0, 1) | długość s | wszystkie znaki przesuwają się o miejsce |
s.find(t) | nawet n · m | dla każdej pozycji porównuje kawałek z t |
string s = "";
for (int i = 0; i < 100000; i++) {
s = s + 'x'; // WOLNO: za każdym razem kopia całego s
}
string t = "";
for (int i = 0; i < 100000; i++) {
t += 'x'; // SZYBKO: dokłada jeden znak
}
Oba fragmenty budują napis ze stu tysięcy liter x, ale pierwszy jest wielokrotnie wolniejszy. s = s + 'x' najpierw tworzy nowy napis — kopię całego s z dodanym znakiem — a potem przepisuje go z powrotem do s. Przy ostatnich obrotach to kopiowanie stu tysięcy znaków naraz, a w sumie — około pięciu miliardów kopiowań. t += 'x' dokłada jeden znak na końcu.
Ta sama pułapka dotyczy doklejania z przodu (w = c + w) — dla długich napisów lepiej zbudować wynik od końca przez +=, a potem odwrócić go raz pętlą ze swap.
main: ios_base::sync_with_stdio(false); i cin.tie(nullptr);? Działają też z getline i wczytywaniem napisów. Po ich dopisaniu nie mieszaj już cin i cout z scanf i printf.
Tablica napisów i liczenie słów
Ostatni schemat: ile razy występuje każde słowo? Liter jest 26, więc wystarczyła tablica liczników. Różnych słów może być bardzo dużo, więc tak się nie da. Na razie — zanim poznasz struktury, które zrobią to szybciej — możesz wczytać słowa do tablicy i dla każdego policzyć, ile razy występuje, porównując je ze wszystkimi. Dla tysiąca słów to milion porównań: w sam raz.
int n;
cin >> n;
string t[1000];
for (int i = 0; i < n; i++) {
cin >> t[i];
}
string najczestsze = "";
int rekord = 0;
for (int i = 0; i < n; i++) {
int ile = 0;
for (int j = 0; j < n; j++) {
if (t[j] == t[i]) ile++;
}
if (ile > rekord || (ile == rekord && t[i] < najczestsze)) {
rekord = ile;
najczestsze = t[i];
}
}
cout << najczestsze << " " << rekord << "\n";
Dla każdego słowa t[i] wewnętrzna pętla liczy, ile słów jest mu równych. Rekord zmienia się, gdy słowo występuje częściej — albo tyle samo razy, ale jest wcześniej w alfabecie. Dzięki temu przy remisie wygrywa słowo alfabetycznie pierwsze.
To rozwiązanie liczy każde słowo tyle razy, ile razy występuje — „kot” trzy razy. To marnotrawstwo, ale nieszkodliwe. W lekcji o mapach poznasz strukturę, która policzy słowa w jednym przejściu, nawet dla miliona słów.
Najpierw odpowiedz w myślach — rozpisz sobie znaki napisu w pudełkach z numerami i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.
int ile[26] = {};
string s = "banana";
for (char c : s) ile[c - 'a']++;
cout << ile[0] << ile[1] << ile['n' - 'a'];
Pokaż odpowiedź
'n' - 'a' to n (2 razy).string s = "xyz";
for (char &c : s) {
c = 'a' + (c - 'a' + 2) % 26;
}
cout << s;
Pokaż odpowiedź
char c = 'b';
int k = 3;
cout << (char)('a' + (c - 'a' + 26 - k) % 26);
Pokaż odpowiedź
string sam = "aeiouy";
cout << (sam.find('o') != string::npos) << (sam.find('k') != string::npos);
Pokaż odpowiedź
find ją znajduje. k nie — find zwraca npos.string s = "abcab";
int p[6];
p[0] = 0;
for (int i = 1; i <= 5; i++) {
p[i] = p[i - 1] + (s[i - 1] == 'a');
}
cout << p[5] - p[1];
Pokaż odpowiedź
p[5] - p[1] to liczba liter a wśród znaków od 2. do 5. (b, c, a, b) — jedna.string s = "abaaa";
int k = 3, ile = 0;
for (int i = 0; i < k; i++) ile += (s[i] == 'a');
int best = ile;
for (int i = k; i < 5; i++) {
ile += (s[i] == 'a');
ile -= (s[i - k] == 'a');
if (ile > best) best = ile;
}
cout << best;
Pokaż odpowiedź
string s = "ala";
s = s + 'x';
s += 'y';
cout << s.length();
Pokaż odpowiedź
int ile[128] = {};
string s = "A a!";
for (char c : s) ile[c]++;
cout << ile['a'] + ile['A'] << ile[' '];
Pokaż odpowiedź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
Baza zadań: napisy w praktyce
Znasz już wszystko, co potrzebne: napis jako rząd znaków, wczytywanie słów, wierszy i całego tekstu, rodzaje znaków i toupper, budowanie i zmienianie napisów, kolejność słownikową, metody substr, find, erase, insert i replace, liczby zapisane jako napisy, a do tego liczniki liter, szyfry, okna i sumy prefiksowe. Czas na zadania, które łączą kilka z tych rzeczy naraz. Są ułożone od najłatwiejszego do najtrudniejszego: najpierw rozgrzewka z jednym pomysłem, potem zadania średnie — szyfr harcerski, PESEL, alfabet Morse’a, krzyżówka, numer konta — a na końcu trudne, z olbrzymimi liczbami, palindromami, zawijaniem tekstu i wielkim finałem.
Przy każdym zadaniu widać, jakich zagadnień używa — także tych z poprzednich lekcji, jak modulo czy tablice. Jeśli coś brzmi obco, wróć do odpowiedniej części — mapa lekcji jest na górze strony. A tu masz najważniejsze schematy z lekcji w jednym miejscu:
Ściąga: gotowe schematy z napisami
Podstawy
int n = s.length(); // zawsze int! s[0] s[n - 1] s[n / 2] s.empty() string(k, '*') string t = s; // osobna kopia
Indeksy od 0 do n - 1. Polskie litery zajmują po dwa znaki.
Wczytywanie
cin >> s; // słowo getline(cin, s); // wiersz while (cin >> s) … // do końca cin >> n; cin.ignore(); // przed getline
Po cin >>, a przed getline — cin.ignore() albo getline(cin >> ws, s).
Rodzaje znaków
isdigit(c) isalpha(c) isalnum(c) isupper(c) islower(c) isspace(c) s[i] = toupper(s[i]); c - '0' c - 'a' '0' + d
is… zwracają „nie zero”, a nie 1. toupper daje int — w cout rzutuj na char.
Budowanie
string w = ""; w += c; w += "abc"; w = c + w; // z przodu w.pop_back(); // gdy !w.empty()
Plus skleja tylko z prawdziwym string. Liczby: to_string(x).
Porównywanie
a == b a < b swap(a, b) // olbrzymy bez zer na początku: a.length() != b.length() ? a.length() < b.length() : a < b
Kolejność słownikowa do pierwszej różnicy. Wielkie litery przed małymi.
Fragmenty
s.substr(od, ile) s.substr(od) int p = s.find(x); // -1: brak s.find(x, p + 1) s.rfind(x) s.erase(od, ile) s.insert(od, t) s.replace(od, ile, t)
Nigdy if (s.find(x)). Od a do b włącznie: substr(a, b - a + 1).
Liczby i olbrzymy
to_string(x) stoi(s) stoll(s)
r = (r * 10 + (c - '0')) % k;
w = w * 2 + (c - '0'); // z dwójkowego
wynik = (char)('0' + d) + wynik;
Dodawanie i mnożenie pisemne — od końca, z przeniesieniem.
Olimpijskie sztuczki
int ile[26] = {}; ile[c - 'a']++;
c = 'a' + (c - 'a' + k) % 26;
p[i] = p[i - 1] + (s[i - 1] == 'a');
// okno: +wchodzący, -wypadający
Długie napisy: s += c, nie s = s + c.
cin >>), wiersze ze spacjami (getline) czy całość do końca danych — i czy po liczbie trzeba zjeść Enter. 2) Zapisz długość w int n. 3) Zmieniasz znak na znak — pracuj w miejscu. Coś znika albo przybywa — buduj nowy napis. 4) Zanim napiszesz pętlę, sprawdź, czy nie ma gotowej metody: find, substr, replace. 5) Przy każdym s[i + 1], s[i - 1] i substr sprawdź brzegi — pusty napis, jeden znak, fragment na samym końcu. 6) Pytanie o to, ile jakich liter? Tablica liczników. Dużo pytań o fragmenty? Sumy prefiksowe albo okno. 7) Przetestuj skrajności: jeden znak, same spacje, wielkie i małe litery, liczba na samym końcu tekstu.
Rozgrzewka · zadania 1–10
Jeden pomysł naraz: akronimy, hashtagi, język P, rymy, łańcuch słów, wisielec, litery po kolei i SMS na starym telefonie.
Średnie · zadania 11–20
Kilka sztuczek naraz: GA-DE-RY-PO-LU-KI, czas trwania filmu, nawiasy, liczby rzymskie, kalkulator, PESEL, alfabet Morse’a, krzyżówka, obroty napisu i numer konta IBAN.
Trudne · zadania 21–29
Okres napisu, zawijanie wierszy, wzorce z pytajnikami, najdłuższy palindrom, odejmowanie i mnożenie olbrzymów, najdłuższy fragment bez powtórzeń, kwota słownie — a na koniec wielki finał: edytor tekstu.