Операции для типа string. Функции STL

Строки подобно числам можно суммировать и сравнивать. При суммировании двух строк происходит слияние (конкатенация) первой и второй строки. Например, для[29]

string s1 = "Cogito,", s2 = " ergo sum";

string s3 = s1 + s2;            //s3 == "Cogito, ergo sum"

Сравнение двух строк происходит лексикографически, т.е. в алфавитном порядке (как в школьном журнале). Например ”Австралия”<”Австрия”, ”Африка”<”Байкал” и т.д.

Для класса string в STL (Standard Template Library, или стандартная библиотека шаблонов) имеется много полезных функций/

Для определения длины строки можно использовать свойство length() (или его синоним size()). Например,программа

#include <iostream>

using namespace std;

int main(){

string s = "Usus est optimus magister";// лат. «опыт — лучший

                                // учитель»

cout << "Длина строки \"" << s <<"\" равна " << s.length();

}

выведет

Длина строки "Usus est optimus magister" равна 25

Свойство empty() булевского типа принимает значение true, если строка пуста.Например, фрагмент программы будет каждый раз повторно требовать ввода имени, пока строка name остается пустой.

string name;

while(name.empty){

cout << "Введите имя:";

     cin >> name;

}

Свойство clear() очищает строку, т.е. длина строки length() становится нулем, а свойство empty() будет возвращать true.

string s="Quod erat demonstrandum";//лат. «Что и требовалось доказать»

s.clear();                //строка s теперь пуста

Для вставки подстроки в строку применяется метод insert(). Он имеет несколько форм использования. Например, программа

#include<iostream>

using namespace std;

int main(){

string s = "Everybody’s business is business";

s.insert(24,"nobody’s ");

cout<< s;

}

выведет английскую поговорку «Дело всех – ничье дело»

Everybody’s business is nobody’s business

В данном случае подстрока "nobody’s " была вставлена, начиная с 24 символа. Можно вставлять не только подстроку целиком, но и её часть. Например, программа

#include <iostream>

using namespace std;

int main(){

string s1 = "Everybody’s business is business",

       s2 = " nobody’s ";

s1.insert(23, s2, 0, 3);

cout << s1;

}

выведет

Everybody’s business is no business

В строку s1 с 23 символа были вставлены из строки s2 три символа, начиная от нулевого.

Если нужно добавить всего один символ к концу строки, можно использовать метод push_ back. Так в результате выполнения фрагмента

strings = "Dixi";

s.push_back('!');

к строке “Dixi”[30]добавится восклицательный знак.

Для поиска подстроки в строке применяется метод find(). Например, в результате выполнения программы

#include <iostream>

using namespace std;

int main(){

string stars = "ACAMAR, ACHERNAR, ALBIREO, ALCOR, ALDEBARAN, ALGOL, "

   "ANTARES, ARCTURUS, BELLATRIX, BETELGEUSE, CANOPUS, CAPELLA, "

   "CASTOR, DENEB, DENEBOLA, FOMALHAUT, KAUS AUSTRALIS, MARKAB, "

   "MENKAR, MIZAR, POLARIS, POLLUX, PROCYON, REGULUS, RIGEL, "

   "SIRIUS, SPICA, VEGA, VINDEMIATRIX";

cout << stars.find("FOMALHAUT");

}

будет выведено число 137. Т.е. первая найденная подстрока "FOMALHAUT" начинается с символа 137 в строке stars. Обратите внимание, для присвоения переменной типа string очень длинного текста можно этот текст разделить на несколько строк.

Если подстрока отсутствует в строке, то find() вернет значение string:: npos. Например, программа для проверки, встречается ли подстрока substr в строке sможет выглядеть так:

#include <iostream>

using namespace std;

int main(){

string s, substr;

getline(cin, s);

getline(cin, substr);

int pos = s.find(substr);

cout << substr << " в " << s;

if(pos == string::npos) {cout << " не найдена";}

else cout << " найдена в позиции " << pos;

}

Задача №143.  Условия Фано

Условие Фано: для того, чтобы сообщение, записанное с помощью неравномерного по длине кода, однозначно декодировалось, достаточно, чтобы никакой код не был началом другого (более длинного) кода.

Обратное условие Фано требует, чтобы никакой код не был окончанием другого (более длинного) кода.

Для того чтобы сохранилась возможность декодирования, достаточным является соблюдение прямого или обратного условия Фано.

Например, для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код: А – 10, Б – 001, В – 000, Г–110, Д–111. Этот код позволяет однозначно декодировать полученную двоичную последовательность, т.к. для него выполнено прямое условие Фано.

Пусть для некоторого N-символьного алфавита известен двоичный код каждого символа. Укажите, удовлетворяет ли такой метод кодирования прямому условию Фано.

Входные данные

В первой строке записано количество кодируемых символов N, не превышающее 100. В последующих Nстроках записаны коды каждого символа, состоящие исключительно из единиц и нулей.

Выходные данные

Выведите YES, если выполняется прямое условие Фано и NO в противном случае.

Пример

Ввод	Вывод
3 1 00 01	YES
3 1 00 10	NO

Решение

#include <iostream>

using namespace std;

int main() {

string s[100];

int n, i, j;

bool fano = true;

cin >> n;

for(i = 0; i < n; i++){

     cin >> s[i];

     for(j = 0; j < i; j++)

           if(!s[i].find(s[j]) || !s[j].find(s[i])) fano = false;

}

cout << (fano ? "YES" : "NO");

}

Задача №144.  Вставить скобки

(2014 Azerbaijan - Zadeh cup) Милхаузу необходимо на завтра решить задачу, и ему нужна Ваша помощь. Вот задача:

Задана строка, состоящая из скобок. Необходимо превратить ее в правильную строку, вставляя как можно меньшее количество скобок в любую позицию (удалять или изменять существующие скобки нельзя). Правильной является строка, которая удовлетворяет следующим правилам:

1. Пустая строка правильная.

2. Если s правильная, то (s) также правильная.

3. Если s и t правильные, то их конкатенация st правильная.

Например, "(()())", "" и "(())()" правильные строки, а "())(", "()(" и ")" - нет.

Входные данные

Задана строка из скобок, которая содержит от 1 до 50 символов включительно.

Выходные данные

Вывести наименьшее количество скобок, которое следует вставить для того чтобы входная строка стала правильной.

Ввод	Вывод
(()(()	2

Решение

Эту задачу можно решить многими способами. Рассмотрим два из них. Первое решение основывается на поиске и удалении подстроки из открывающей и закрывающей скобки

#include <iostream>

using namespace std;

int main() {

string s;

cin >> s;

while(s.find("()") != string::npos)

   s.erase(s.find("()"),2);

cout << s.length();

}

Второй способ предполагает введение еще одной дополнительной строки, которая будет использоваться как стек

#include <iostream>

using namespace std;

int main() {

string a, stk = "";

cin >> a;

int ptr = 0, len = a.length();

for (int i=0; i < len; i++){

   stk[ptr++] = a[i];

   if (stk[ptr-2] == '('&& stk[ptr-1] == ')') ptr -= 2;

}        

cout << ptr;

}

Задача №145.  Стрелки

Задана последовательность, состоящая только из символов '>', '<' и '-'. Требуется найти количество стрел, которые спрятаны в этой последовательности.

Стрелы – это подстроки вида ‘>>-->‘ и ‘<--<<‘.

Входные данные

Строка, состоящая из символов '>', '<' и '-' (без пробелов). Строка состоит не более чем из 250 символов.

Выходные данные

Единственное число - искомое количество стрелок.

Пример

INPUT.TXT	OUTPUT.TXT
<<<<>>--><--<<--<<>>>--><<<<<	4

Решение

#include<iostream>

usingnamespace std;

string str;

int findArrow(const string substr){

int cnt = 0;

size_t pos = str.find(substr);

while(pos != string::npos) {

   cnt++;

   pos = str.find(substr, pos + 1);

}

return cnt;

}

int main() {

cin >> str;

cout << findArrow(">>-->") + findArrow("<--<<");

}

Задача №146.  Антипробелы

Назовём символ # «антипробелом». Его действие эквивалентно нажатию клавиши Backspace при наборе текста (стирает ближайший символ слева от курсора, если он есть). Выведите строку, содержащую антипробелы, в обычном виде.

Входные данные

Строка, содержащая «антипробелы»

Выходные данные

Строка без «антипробелов» с учетом их действия.

Пример

Ввод	Вывод
Ex##Sia#mm#ple###feropol	Simferopol

Решение

#include <iostream>

using namespace std;

int main(){

string s;

int pos, del;

cin >> s;

while(s.find('#') != string::npos){

   pos = s.find('#');

   del = pos ? 2 : 1;      //сколько символов удалять

   s.erase(pos – del + 1, del);

}

cout << s;

}

Задача №147.  Зачеркивание цифр

Задано некоторое натуральное число N, в котором больше, чем K цифр в десятичной системе счисления. Вычеркните ровно K цифр, так чтобы получившееся число было наибольшим

Входные данные

В первой строке натуральное число K (K ≤ 100). Во второй натуральное число N (10^K < N ≤ 10²⁵⁰)

Выходные данные

Одно число – наибольшее возможное из всех, которые могут быть получены из N вычеркиванием K цифр.

Пример

Ввод	Вывод
1 501	51
2 96781	981

Решение

Очевидно, ограничения для входных данных задачи не позволят использовать стандартные типы. Сохраним число N как строку. В решении нужно удалять не наименьшую цифру, а от начала строки такие символы (цифры), которые меньше следующей. Например, в числе 97823 нужно удалять не 2, что преобразует число в 9783, а 7, что преобразует число в 9823.

#include <iostream>

using namespace std;

int main() {

string n;

int k;

cin >> k >> n;

while(k--){

   bool del = true;             // цифра еще не вычеркнута

   for(int i = 0; n[i+1] && del; i++)

       if(n[i] < n[i+1] && del){ // нашли, какую убрать

           n.erase(i, 1);

           del = false;

       }

   n.erase(n.length() - del);  // если нет, то последнюю

}

cout << n;

}

Задача №148.  Минимальное число (acmp.ru)

(Время: 1 сек. Память: 16 Мб)

Требуется написать программу, которая из цифр двух натуральных чисел создает наименьшее возможное число, сохраняя при этом порядок следования цифр в этих числах.

Входные данные

Входной файл INPUT.TXT содержит два натуральных числа, записанных в двух строках. Числа больше нуля и меньше 10²⁵⁵.

Выходные данные

В единственную строку выходного файла OUTPUT.TXT нужно вывести наименьшее возможное число, удовлетворяющее условию задачи.

Пример

Ввод	Вывод
125 34	12345

Решение

#include <iostream>

#define S(s,k) s.substr(k)

int main(){

std::string a, b;

std::cin >> a >> b;

for(int i = 0, j = 0; a[i] || b[j];)

   std::cout << (!a[i] || S(a, i) + S(b, j) > S(b, j) + S(a, i)

               ? b[j++] : a[i++]);

}

Задача №149.  Подстрока Туэ-Морса

Определим последовательность строк T_n двухбуквенного алфавита {a, b} следующим образом:

 , где:

t_i = a, если двоичная запись числа i содержит чётное число единиц

t_i = b, иначе.

Строки этой последовательности называются строками Туэ-Морса[31].

Например, первые слова последовательности Туэ-Морса:

T₀ = a

T₁ = ab

T₂ = abba

T₃ = abbabaab

Легко определить каждую следующую строку этой последовательности через предыдущую:

a заменяется на ab, а b – на ba.

Дана бесконечная строка Туэ-Морса: abbabaabbaababbabaabab…

Выведите ее содержимое, начиная с символа номер N и заканчивая символом номер M включительно (символы нумеруются с единицы).

Входные данные

В одной строке через пробел два натуральных числа N, M ≤ 10⁵.

Выходные данные

Подстрока строки Туэ-Морса с беЗконечным номером, начиная от символа номер N до символа номер M включительно. В ответе используйте только строчные латинские буквы.

Пример

Ввод	Вывод
239  243	ababb

Решение

Легко увидеть, что каждая следующая строка получается из предыдущей приписыванием к ней её инвертированной копии (т.е. ‘a’ заменяется на ‘b’ и наоборот).

#include <iostream>

using namespace std;

int main() {

string s = "a";

int n, m, len = 1;

cin >> n >> m;

while(m > len){

   for(int i = 0; i < len; i++)

       s.push_back('a'+'b'-s[i]); //инверсия символа{a,b}

   len <<= 1;                   // то же, что len *= 2;

}

cout << s.substr(n - 1, m – n + 1);

}