Тема 1.5. Символьные строки (тексты)

Цель.

Изучение особенностей массивов, содержащих символьную информацию (строки, тексты).

Основные понятия.

Во многих языках программирования для работы с текстами (символьными строками) используются массивы типа charсо специальным символов конца ‘\0’ или специальные классы типаstring. Для них разработано много специальных функций и методов классов. Приведём некоторые из них для символьных массивов:

intstrlen(char*) – функция вычисляет длину строки

char*strcpy(char*,char*) – копирует вторую строку по первому адресу (массивы нельзя присваивать)

intstrcmp(char*,char*) – сравнивает две строки

char*strcat(char*,char*) – присоединяет вторую строку в конец первой

Обычно тексты обрабатываются по символам или по словам (группам символов).

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

gets (char *)

cin.getline (char *, int)

Ключевые слова.

Строка, текст, слово, символ, нулевой символ, адрес, указатель

ПРИМЕР.

Написать программу, которая вычислит и напечатает количество слов в заданном тексте. Текст состоит из последовательности слов, разделённых пробелами. Слово содержит произвольные символы (буквы), отличные от пробела. Слово не является частью другого слова и не содержит в себе другие слова.

Алгоритм.

Будем последовательно выделять каждое слово и вести их подсчёт. Начало слова определяется как не пробел, конец слова находится по пробелу или концу текста. Схема обработки слов может выглядеть так:

ЦИКЛ до конца текст – будет найдено и обработано ровно одно слово

НАЙТИ начало слова (в цикле пропустить все пробелы)

ЕСЛИ достигли конца текста, ТО ВЫХОД из цикла

ЗАПОМНИТЬ позицию начала слова

НАЙТИ конец слова (в цикле пропустить все не пробелы)

ЗАПОМНИТЬ позицию конца слова

ОБРАБОТАТЬ слов – зависит от конкретной задачи

КОНЕЦ_ЦИКЛА

ПЕЧАТЬ результатов

Решение.

Согласно приведённому алгоритму напишем программу. Наша программа будет содержать большой цикл по словам и внутри него два цикла для поиска начала и конца слова. В зависимости от задачи циклы могут быть и в пункте ОБРАБОТАТЬ СЛОВО.

// C++

# include <iostream>

# include <cstring>

# include <cstdlib>

using namespace std;

const int N = 100000; // заранее заведём большой массив для текста

char text [N];

int main ()

{

setlocale (LC_ALL, "RUS");

cout << "Подсчёт количества слов в тексте." << endl;

cout << "Введите текст." << endl;

cin.getline (text, N-1); // текст может содержать любые символы

int kol=0;

// ЦИКЛ до конца текст – будет найдено и обработано ровно одно слово

for ( int i=0; text [i] != 0; )

{

// НАЙТИ начало слова (в цикле пропустить все пробелы)

for ( ; text [i] == ' '; i++ )

;

// ЕСЛИ достигли конца текста, ТО ВЫХОД из цикла

if (text [i] == 0 ) break;

// НАЙТИ конец слова (в цикле пропустить все не пробелы)

for ( ; text [i] != 0 && text [i] != ' '; i++ )

;

kol++; // ОБРАБОТАТЬ слово – зависит от конкретной задачи

}

cout << kol << endl;// ПЕЧАТЬ результатов

system ("PAUSE");

return 0;

}

// C#

using System;

class Program

{

static void Main (string [] args)

{

Console.WriteLine ("Подсчёт количества слов в тексте.");

Console.WriteLine ("Введите тексте");

string s = Console.ReadLine ();

int kol=0;

for ( int i=0; i < s.Length; )

{

for ( ; (i < s.Length) && (s [i] == ' '); i++ )

;

if ( i == s.Length ) break;

for ( ; (i < s.Length) && (s [i] != ' '); i++ )

;

kol++;

}

Console.WriteLine (kol);

Console.ReadKey ();

}

}

Задачи для обязательного решения.

1.5.1.1. Вычислить и напечатать сколько раз в заданном тексте встречаются гласные буквы.

Исходные данные:

Пример простого текста

Результат:

7

1.5.1.2. В заданном тексте заменить все строчные буквы на прописные и наоборот.

Исходные данные:

Пример Простого Текста

Результат:

пРИМЕР пРОСТОГО тЕКСТА

1.5.1.3. Сравнить два слова одинаковой длины на совпадение соответствующих букв, не различая регистр букв. Если слова одинаковые напечатать «ДА», иначе напечатать

«НЕТ» (или количество различий).

Исходные данные:

Пример

пРИМЕР

Результат: 7

ДА

1.5.1.4. Вычислить и напечатать сколько раз в заданном тексте встречается каждый символ. Если какой-то символ не встречается в тексте, про него ничего печатать не надо (встречается 0 раз).

Исходные данные:

текст

Результат:

е 1

к 1

с 1

т 2

1.5.1.5. Написать программу для реализации функции intstrlen(char*) – вычисляет длину символьной строки.

Исходные данные:

Пример текста

Результат:

15

1.5.1.6. Написать программу для реализации функции voidstrcpy(char*,char*) – копирует символьную строку из одного места в другое.

Параметры при вызове:

Пример строки

Результат:

Пример строки

1.5.1.7. Написать программу для реализации функции voidstrcat(char*,char*) – прицепляет вторую строку в конец первой.

Параметры при вызове:

Пример строки

Другая строка

Результат:

Пример строки Другая строка

1.5.1.8. Написать программу для реализации функции intstrcmp(char*,char*) – сравнивает две строки. Если они в точности совпадают, возвращает 0, если первая строка по алфавиту должны стоять раньше второй, то возвращает -1, если первая строка по алфавиту должны стоять позже второй, то возвращает 1.

Параметры при вызове:

Пример строки

Другая строка

Результат:

-1

1.5.1.9. Дана символьная строка, содержащая некоторую формулу с круглыми скобками. Написать программу, которая напечатает «ОК», если скобки расставлены правильно, и «НЕТ» в противном случае.

Исходные данные:

(а+в)*(с-)

Результат:

ОК

1.5.1.10. Дан текст, состоящий из слов. Напечатать каждое слово в отдельной строке

Исходные данные:

Пример простого текста

Результат:

Пример

простого

текста

1.5.1.11. Дан текст, состоящий из слов. Напечатать его, оставляя между словами ровно по одному пробелу.

Исходные данные:

Пример простого текста

Результат:

Пример простого текста

1.5.1.12. В тексте найти и напечатать самое длинное слово.

Исходные данные:

В тексте найти и напечатать самое длинное слово

Результат:

напечатать

1.5.1.13. Глубина вложения скобок. Определить максимальную глубину вложения круглых скобок в некоторой формуле с правильной расстановкой скобок.

Исходные данные:

((()(())())())

Результат:

4

1.5.1.14. Удалить заданное слово из текста (по номеру или позиции начала). Нумерация слов с 1.

Исходные данные:

В тексте найти и напечатать самое длинное слово

5

Результат:

В тексте найти и самое длинное слово

1.5.1.15. Удалить все вхождения заданного слова из текста. В первой строке задаётся текст, состоящий из слов, разделённых сериями пробелов, во второй – искомое слово.

Исходные данные:

В тексте и найти и напечатать самое длинное слово и кое-что ещё

и

Результат:

В тексте найти напечатать самое длинное слово кое-что ещё

Задачи для самостоятельного решения.

1.5.2.1. Дан текст, состоящий из слов. Найти и напечатать наибольшую цепочку слов, в которой каждое следующее начинается на ту же букву, на которую кончается предыдущее слово.

Исходные данные:

Если блин нет то напечатать -1

Результат:

блин нет то

1.5.2.2. Дан текст, состоящий из слов. Найти и напечатать слово с наибольшим числом буквы А (прописных и строчных).

Исходные данные:

В тексте найти и напечатать самое длинное слово

Результат:

напечатать

1.5.2.3. Дан текст, состоящий из слов. Найти и напечатать слово с наибольшим числом различных букв и это количество.

Исходные данные:

В тексте найти и напечатать самое длинное слово

Результат:

напечатать 7

1.5.2.4. Дан текст, состоящий из слов. Напечатать все слова буквами наоборот.

Исходные данные:

Пример простого текста

Результат:

ремирП огтсорп атскет

1.5.2.5. Дан текст, состоящий из слов. Напечатать все слова в порядке от последнего к первому.

Исходные данные:

Пример простого текста

Результат:

текста простого пример

1.5.2.6. Дана символьная строка, содержащая некоторую формулу с тремя типами скобок – круглыми, квадратными и фигурными. Написать программу, которая напечатает «ОК», если скобки расставлены правильно, и «НЕТ» в противном случае.

Исходные данные:

([]{[]})

Результат:

OK

1.5.2.7. В тексте найти и напечатать все различные слова по одному в строке. Разделители между словами – только пробелы.

Исходные данные:

Пример простого текста, не содержащего в себе другого текста

Результат:

Пример

простого

текста,

не

содержащего

в

себе

другого

1.5.2.8. Дан текст, состоящий из слов. Напечатать слова в несколько строк шириной W, вставляя лишние пробелы между словами. Начало слова – первый символ в строке, конец слова – последний. Перед текстом в отдельной строке задаётся ширина W.

Исходные данные:

Результат:

1.5.2.9. В тексте встречаются числа. Напечатать самое большое.

Исходные данные:

Пример текста с 3 или 15 числами

Результат:

15

1.5.2.10. Даны два слова (текста) одинаковой длины. Если они состоят из одинакового набора символов, то напечатать «ДА», иначе – напечатать «НЕТ».

Исходные данные:

ABBA

BАВA

Результат:

ДА

1.5.2.11. Дано слово. Если из него можно получить палиндром, переставляя некоторые буквы, то напечатать один из них. Если нельзя, напечатать слово «НЕТ».

Исходные данные:

ABRACADABRA

Результат:

НЕТ

1.5.2.12. Даны два слова (текста). Найти и напечатать номер позиции, начиная с которой первое слово входит как часть во второе. Если нет, то напечатать -1. Нумерация с 0.

Исходные данные:

ABRACADABRA

BRA

Результат:

1

1.5.2.13. Даны два слова (текста). Найти и напечатать сколько раз первое слово входит как часть во второе.

Исходные данные:

ABRACADABRA

BRA

Результат:

2

1.5.2.14. Дан словарь правильных слов и текст. Напечатать все слова из текста, которые содержат более одной ошибки типа - неправильная буква, пропущена буква, лишняя буква. В первой строке задаётся количество слов в словаре n(n<= 1000). Далее следуютnстрок, содержащих слова из словаря по одному в строке. Длина каждого слова не превосходит 20. Слова состоят только из строчных латинских букв. В последней строке задаётся текст длиной до 100000 символов из строчных латинских букв и знаков препинания.

Исходные данные:

5

the

word

this

is

world

thit is hte uorlt

Результат:

hte

uorlt

1.5.2.16. Дан словарь из нескольких слов и некоторый набор букв. Напечатать все слова из этого словаря, которые можно составить из заданного набора букв. В первой строке задаётся количество слов в словаре n(n<= 1000). Далее следуютnстрок, содержащих слова из словаря по одному в строке. Длина каждого слова не превосходит 20. Слова состоят только из строчных латинских букв. В последней строке задаётся набор строчных латинских букв длиной до 26 символов.

Исходные данные:

5

the

word

this

is

world

ihostwr

Результат:

this

word

is

1.5.2.17. Дан текст из слов, разделенных пробелами. Удалить слово с указанным номером.

Исходные данные:

We are the world

3

Результат:

We are world

1.5.2.18. Дан текст из слов, разделенных пробелами, и ещё одно слово. Вставить новое слово после слова с указанным номером без использования дополнительных массивов.

Исходные данные:

We are world

the

2

Результат:

We are the world

1.5.2.19. Дан текст из слов, разделенных пробелами. Поменять местами два слова с указанными номерами без использования дополнительных массивов.

Исходные данные:

We are the world

1 3

Результат:

the are We world

1.5.2.20. Анаграмма. Пусть задано некоторое слово, состоящее из букв английского алфавита длинной не более 80 символов (например, “WORD”). Рассмотрим набор возможных перестановок, состоящих из букв данного слова (например, “RDOW”, “WODR” и т.д.). Требуется выбрать из этого множества слово, следующее по алфавиту за исходным. В единственной строке записано слово, не последнее по алфавиту среди возможных его перестановок. Вывести следующее слово по алфавиту.

Исходные данные:

WORD

Результат:

WDRO

1.5.2.21. Степень строки. Пусть задана строка s = s₁s₂...s_n. Назовем ее k-ой (k > 0) степенью s^kстроку s^k= s₁s₂. . .s_ns₁s₂. . .s_n......s₁s₂...s_n(k раз). Например, третьей степенью строки abc является строка аbсаbсаbс. Корнем k степени из строки s называется такая строка t (если она существует), что t^k= s. Написать программу, находящую степень строки или корень из нее. Первая строка содержит строку s, она содержит только маленькие буквы латинского алфавита и имеет ненулевую длину, не превосходящую 1000.

Вторая строка входного файла содержит целое число k ≠ 0, |k| < 100001. Если k > 0, то необходимо найти k-ую степень строки s, если k < 0, то необходимо найти корень степени |k| из s. Вывести строку, являющуюся ответом на задачу. Если длина ответа превосходит 1023 символа, выведите только первые 1023 символа. Если искомой строки не существует — выведите NO SOLUTION.

Исходные данные:

abcdabcd -2

Результат:

abcd

Продвинутые задачки.

1.5.3.1. Дана символьная строка, состоящая из прописных латинских букв. Напечатать «ДА», если она является палиндромом, если игнорировать пробелы и не учитывать регистр букв.

Исходные данные:

Вона Бирганов а вона Грибанов

Результат:

ДА

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

Исходные данные:

())(

Результат:

2

1.5.3.3. Палиндромом называется строка, которая одинаково читается как слева направо, так и справа налево. Подпалиндромом данной строки называется последовательность символов из данной строки, не обязательно идущих подряд, являющаяся палиндромом. Например, HELOLEH является подпалиндромом строки HTEOLFEOLEH. Напишите программу, находящую в данной строке подпалиндром максимальной длины.

Исходные данные:

HTEOLFEOLEH

Результат:

HELOLEH

1.5.3.4. Выкинуть из текста программы (много строк) примечания. На вход подаётся последовательность строк, некоторой синтаксически правильной программы на языке Си++.

Исходные данные:

int main () /* главная функция */

{

return 0; // it’s result

}

Результат:

int main ()

{

return 0;

}

1.5.3.5. В тексте поменять местами два слова по заданным их номерам. В первой строке задаётся текст, в котором слова разделены сериями пробелов, во второй строке заданы через пробел два натуральных числа – номера меняемых слов. Напечатать текст до и после обмена слов местами. Если слово с каким-то номером отсутствует в тексте, то в тексте ничего не надо менять.

Исходные данные:

Пример простого и короткого текста

2 4

Результат:

Пример короткого и простого текста

1.5.3.6. Абракадабра. Последовательность из латинских букв строится следующим образом. Вначале она пуста. На каждом последующем шаге последовательность удваивается, после чего к ней слева дописывается очередная буква латинского алфавита (a, b, c, …). Ниже приведены первые шаги построения по-следовательности:

Шаг 1. a

Шаг 2. baa

Шаг 3. cbaabaa

Шаг 4. dcbaabaacbaabaa

…………………………

Написать программу, которая по заданному числу N находит символ, который стоит на N-ом месте в последовательности, получившейся после 26-го шага. В единственной строке записано число N (1 <= N < 2²⁶). Вывести символ, стоящий в N-й позиции получившейся последовательности.

Исходные данные:

4

Результат:

w

1.5.3.7. Охрана. На секретной военной базе работает N охранников. Сутки поделены на 10000 равных промежутков времени, и известно когда каждый из охранников приходит на дежурство и уходит с него. Например, если охранник приходит в 5, а уходит в 8, то значит, что он был в 6, 7 и 8-ой промежуток. В связи с уменьшением финансирования часть охранников решено было сократить. Укажите: верно ли то, что для данного набора охранников, объект охраняется в любой момент времени хотя бы одним охранником и удаление любого из них приводит к появлению промежутка времени, когда объект не охраняется. В первой строке записано натуральное число K (1 ≤ K ≤ 100) – количество тестов в файле. Каждый тест начинается с числа N (1 ≤ N ≤ 10000), за которым следует N пар неотрицательных целых чисел A и B - время прихода на дежурство и ухода (0 ≤ A < B ≤ 10000) соответствующего охранника. Все числа во входном файле разделены пробелами и/или переводами строки. Вывести K строк, где в M-ой строке находится слово Accepted, если M-ый набор охранников удовлетворяет описанным выше условиям. В противном случае выведите Wrong Answer.

Исходные данные:

2 3 0 3000 2500 7000 2700 10000 2 0 3000 2700 10000

Результат:

Wrong Answer Accepted

1.5.3.8. Строки. Циклическим сдвигом строки s называется строка s_ks_k+1s_k+2…s_|s|s₁s₂…s_k-1для некоторого k, здесь |s| - длина строки s. Подстрокой строки s называется строка s_is_i+1…s_j-1s_jдля некоторых i и j. Вам даны две строки a и b. Выведите количество подстрок строки a, являющихся циклическими сдвигами строки b. Первая строка содержит строку a (1 ≤ |a| ≤ 1000). Во второй строке записана строка b (1 ≤ |b| ≤ min(100,|a|)). Обе строки состоят только из символов латинского алфавита и цифр.

Исходные данные:

aAaa8aaAa aAa

Результат:

4