Если задача на олимпиаде требует работу со строками, то всегда возникают некоторые проблемы с оптимизацией и быстрой ее реализацией. Если вы знаете Паскаль и Си (С++), то что выбрать?
В Паскале тип string работает как массив и хранит до 255 символов. Нумерация символов в строке начинается с 1. А в нулевом номере хранится символ, код которого отвечает за длину строки. В Си (точнее в С++) тоже есть тип string, но это класс и работать нужно со свойствами и методами этого класса.
Ели строка длиннее 255 символов, то строку можно сохранить как массив символов типа char (как в Си). Но в Си строка символов - это указатель, т.е. адрес памяти, с которого начинается строка, а заканчивается строка символом с нулевым кодом или символом конца строки '\0' (
и об этом нужно всегда помнить!). Если его нет, то при выводе может выйти весь мусор, который находится в памяти компьютера, до тех пор пока не найдется этот символ (соответствующий ему нулевой байт).
Иногда по задаче даже не надо всю строку хранить, достаточно работать с одним символом типа char. В Си один символ заключается в апострофы, а строка - в кавычки. В Паскале - в любом случае - апострофом. Кроме этого в Си тип char - это целое со знаком в один байт, поэтому для русских букв (которые начинаются после 127 кода) при считывании получим отрицательный код. Чтобы этого избежать - объявляем как unsigned char.
Существует проблема ввода/вывода русских символов в современных средах. Так в среде Lazarus используется кодировка UTF8, которая отводит 2 байта под один символ, а все функции со строками языка Паскаль в основном работают в кодировке ANSI, поэтому нужно в начале перевести строку с помощью функции utf8toansi в привычную для Паскаля кодировку. Та же проблема возникнет и в среде CodeBlocks при написании программ с русскими строками (даже при выводе). В этом случае можно поменять кодировку самого проекта или вставить функцию setlocale(LC_ALL,"Russian"). Не забудьте подключить библиотеку locale.h. Конечно можно написать свою функцию декодирования, но это займет время, которое очень дорого стоит во время олимпиады.
Приведем стандартные алгоритмы при работе со строками, которые очень часто встречаются в олимпиадных задачах:
- Найти количество символов в строке
- Заменить символ в строке
- Удалить символ в строке
- Переставить символы в строке наоборот
- Найти количество подстрок в строке
- Удалить заданную строку d в строке s
- Вставить заданную строку d в строку s
- Заменить подстроку на заданную строку
- Вывести все слова в тексте, разделенные пробелом или иным символом
- Выделить цифры/число из строки
- Вывести число по заданному формату
- Определить дату/время по введенной строке
Каждая из этих задач по разному выполняется в Паскале и в Си. Если представить строку как массив символов, то разницы будет мало. Нужно сделать перебор каждого символа последовательно, как в массиве, если мы точно знаем сколько символов в строке. При этом ввод строки можно осуществить посимвольно. Если считывать всю строку, то в Паскале - это просто readln(s), а в Си - при потоковом вводе (с помощью cin) учитывается пробел, поэтому, если в строке есть пробелы, а нужно считать всю строку целиком, то используют специальную процедуру (например, getline). Но при этом конец строки не считывается, как в Паскале, его при выводе нужно добавлять самим (и об этом все время помнить!). Для определении количества символов обычно используют стандартные библиотеки: length(s) в Паскале, strlen(s) в С, s.length или s.size в С++.
Кроме этого при работе с файлами есть свои заморочки: проверка конца строки (коду 10, а не 13 как для Enter, или EOLN), проверка конца файла (EOF).
Описание строк
Паскаль:
var s:string; //строка с переменной длиной
a:string[100];//строка с максимальной длиной строки 100
b:array [1..500] of char;//массив из 500 символов
c:char; //один символ
С:
unsigned char c; //один символ в кодировке ANSI
char d[]="programs for school";//строка сразу задана
char s[100]; // для строки выделяем 100 символов
c=&d; // передаем указатель строки
d переменной
с.
char* t;//строка - указатель на первый символ.
t=(char*) malloc(10);//выделяем память под 10 символов
free(t); //освобождение памяти
C++:
string a;//описание строки а как экземпляр класса string
char *c; /* указатель на начало строки, пока равен NULL (нулевой адрес, который ни на что не указывает)*/
с=new char [100]; /* теперь выделили для хранения строки 100 байт и
с указывает на адрес начала строки.*/
delete c[]; //освобождение памяти
Ввод и вывод строк. Определение длины строки.
Паскаль:
readln(s); //ввод строки s
writeln(s);//вывод строки s
ls:=ord(s[0]);//длина строки s
readln(a); //ввод строки a и только до 100 символов
writeln(a);//вывод строки a
la:=length(a);//длина строки a
l:=0;
while not eoln do begin //
read(c);//посимвольный ввод строки
inc(l);//длина строки (учтите, что символов в строке/массиве не более 500)
b[l]:=c;
end;
readln;//обязательно перейдите на следующую строку
for i:=1 to l do write(b[i]);//посимвольный вывод
writeln; //переход на новую строку
var x,code:integer;y:real;
// считываем только первое найденное число
{1 вариант}
s:='';//пустая строка
while not eoln do begin
read(c);
if c in ['0'..'9'] then s:=s+c //проверка на цифры
else break;
end;
val(s,x,code);//перевод из строки в число
if code=0 then write('целое число - ' , x);
{2 вариант}
//выделяем из строки число, удаляя все не числовые символы
readln(s);
repeat
val(s,y,code);
if code>0 then delete(s,code,1);//удаляем не числовой символ
until code=0;
write('не всегда целое число - ' , y);
//перевод числа x в строку s
str(x,s); str(y:0:2,a);
s:=s+' шт. за '+a+' руб.';
writeln(s);
//одна цифра в символ
x:=6;
c:=chr(ord('0')+6);
//цифра как символ в число
read(c);
x:=ord(c)-ord('0');
var hh,mm,ss,i,x:integer;
//ввод и вывод времени hh:mm:ss или даты dd.mm.yyyy
hh:=0;
for i:=1 to 2 do begin
read(c);
x:=ord(c)-ord('0');
hh:=hh*10*(i-1)+x;//собираем цифры в число
end;
read(c);//пропускаем разделитель времени
s:='';
for i:=1 to 2 do begin
read(c);
s:=s+c;
end;
//подключите модуль system (работает в среде FreePascal, Lazarus)
//strtoint - функция перевода из строки в целое
//strtofloat - функция перевода из строки в вещественное
//inttostr - функция перевода из целого в строку
//floattostr - функция перевода из вещественного в строку
mm:=strtoint(s);
read(c);//пропускаем разделитель времени
readln(ss);//оставшееся число считываем как целое
writeln(hh,':',mm,':',ss);
C:
Для ввода и вывода строки нужно учитывать следующее: есть ли в строке пробелы и оканчивается ли строка после ввода символом конца строки.
1) Можно считать как элементы массива и в конце добавить символ конца строки
2) Используя формат для ввода и вывода строки "%s"
3) Используя потоковый ввод и вывод для строки, содержащей пробелы
#include <stdio.h>
char с='5', t[]="school";
printf ("символы: %c %c %c\n", 'a', 65, c);
printf ("строка: %s \n", t);
scanf("%s",t); //считывает до первого пробела
scanf("%10s",t);//считает не более 10 символов
scanf("%c",&c);
//посимвольный ввод строки
int i;
char s[20];
for (i=0; (s[i] = getchar()) != '\n'; i++);
s[i] = '\0';
printf("\n%s\n", s);
gets(s); //ввод строки с пробелами не включая нулевой символ '\0', длина считываемой строки не ограничена, поэтому, если выделено 20 строк, а введено более, то считает всю строку "куда-нибудь в память", что может привести к непредвиденным ситуациям.
puts(s);//вывод строки с переходом на новую строку
//ввод строки s с указанным максимально возможным размером size-1
fgets(s, size, stdin);
int k = strlen(s); // Длина строки
if((k > 0) && (s[k-1] == 10))
{
k--;
s[k] = '\0';}
/*Функция fgets() имеет побочный эффект. Кроме полезной информации, что была набрана с клавиатуры, в конец строки будет помещён символ с кодом 10, а только затем символ с кодом 0. Для каких-то задач это не существенно, но лучше всегда удалять этот "мусор": в позицию символа с кодом 10 записывать нуль-символ.*/
k=isalpha(c);//проверка того, что символ — латинская буква. Здесь k будет не равно 0, если в переменой c хранится символ — латинская буква, и равно 0 — в противном случае.
k=isdigit(c);//проверка того, что символ — это цифра. Результат — не 0, если в c находится символ цифры, и 0 — если это не так.
//преобразование из числа в строку
char str[50];
int i=15;
int j;
sprintf(str, "%d", i); // Записать в str строковое представление i
sscanf(str, "%d", &j); // Записать в j число, содержащееся в строке str
sprintf(str, "i=%d and j=%d", i, j); // содержимое str: "i=15 and j=15"
//преобразование из строки в число
double d=atof("23.4");
int i=atoi("123");
long l=atol("100000000");
//Заполняем s символьной строкой "ABCD". После выхода из цикла переменная i равна 4.
// В эту позицию и записываем нуль-символ.
char s[6];
int i;
for(i = 0; i < 4; i++)
s[i] = i + 'A';
s[i]='\0';
С++:cin >>a; //ввод слова до пробела
int i, l=a.size();//размер строки
cout<<"длина строки: "<<a<<"\n равна "<<l<<" или "<<a.length()<<endl;
for (i=0;i<l;i++) cout<<a[i]<<endl;//
посимвольный вывод
//ввод и вывод всей строки вместе с пробелами до нажатия Enter
string line;
getline (cin, line);
cout << line << endl; //
внимание! перевод строки не считывается.
//посимвольный ввод и вывод до нажатия клавиши Enter (код 10)
while ( (c=cin.get()) != 10)
cout.put(c);
cout<<endl;
// считываем только числа (нужна библиотека sstream)
string mystr; float price=0; int quantity=0;
cout << "Enter price: "; getline (cin,mystr);
stringstream(mystr) >> price;
cout << "Enter quantity: "; getline (cin,mystr);
stringstream(mystr) >> quantity;
cout << "Total price: " << price*quantity << endl;
double aa=5.5123;
int bb=10;
string ss="74326.46238",dd="123";
//перевод из строки dd в число bb
stringstream(dd)>>bb;
cout<<'\n'<<bb;
//перевод из строки ss в число aa
istringstream ins;
ins.str(ss);
ins>>aa;
cout<<'\n'<<aa;
//перевод из числа bb в строку ss
bb=456;
ostringstream oss;
oss<<bb;
ss=oss.str();
cout<<endl<<ss;
//ввод и вывод времени и даты по формату
int mm, hh, ss, d, m, y;
cout<<"введите время по формату час:мин:сек -> ";
cin >>hh>>c>>mm>>c>>ss;
cout<<hh<<'-'<<mm<<'-'<<ss<<endl;
cout<<"введите дату по формату день/месяц/год:";
cin >>d>>c>>m>>c>>y;
cout<<d<<'-'<<m<<'-'<<y<<endl;
Работа с текстовыми файлами
Паскаль:
Var f:text;
assign(f,'input.txt');reset(f);
readln(f,s);
close(f);
assign(f,'output.txt');rewrite(f);
writeln(f,s);
close(f);
//стандартный ввод/вывод
assign(input,'input.txt');reset(input); //если закоментировать, то ввод с клавиатуры,
assign(output,'output.txt');rewrite(output);// а вывод на экран
readln(s);//input и output не объявляем и не упоминаем в командах!
writeln(s);
В среде Lazarus:
вместо text используют textfile
вместо assign используют assigntfile
вместо close используют closefile
С:
FILE *f;
if((f=fopen("output.txt", "w"))==NULL) //открыть файл для записи
{
printf("He удается открыть файл.\n");
exit(1);
}
fprintf(f, "%s", s);
fclose(f);
f=fopen("input.txt","r");//открыть файл для чтения
fscanf(f, "%s", s);
freopen("input.txt","r",stdin); //стандартный поток ввода/вывода
freopen("output.txt","w",stdout);
scanf("%s",s);
printf("%c",c);
//чтение одного символа из файла
c=fgetc(f);
c=fgetc(stdin);//из стандартного потока ввода данных
//вывод одного символа в файл
fputc(c,f);
fputc(c,stdout);//в стандартный поток вывода данных
fgets(s, n, f);//Чтение строки из файла f размером не более n-1
C++:
//вывод строк в файл
string lines;
ofstream myfile ("example.txt");
if (myfile.is_open()) {
myfile << "This is a line.\n";
myfile << "This is another line.\n";
myfile.close(); }
else
cout << "Unable to open file";
//ввод строк из файла
ifstream myfile ("example.txt");
if (myfile.is_open()) {
while ( myfile.good() ) {
getline (myfile,lines);
cout << lines << endl; }
myfile.close(); }
else
cout << "Unable to open file";
//посимвольный ввод и вывод из файла пока не обнаружится конец файла EOF
ifstream in("input.txt");
ofstream out("output.txt");
while ( (c=in.get()) != EOF)
cout.put(c);
cout<<endl;
Стандартные библиотеки при работе со строками:
Паскаль:
l:=length(s)- длина строки s
p:=pos(s1,s) - позиция подстроки s1 в строке s - всегда первое вложение!
s1:=copy(s,index,count) - выделение из строки s подстроки длины count, начиная с позиции index
delete(s,index,count); - удаление из строки s подстроки длины count, начиная с позиции index
insert(p,s,index); - вставка подстроки p в строку s начиная с позиции index
С:
char *u;
strlen(s) - длина строки без нулевого символа
strcpy(d,s) - копирует строку s в d (при этом не добавляется знак конца строки )
strcpy(d,s,n) - копирует строку s в d c максимально возможным количеством символов n при копировании
strcat(d,s) - соединяет строки d и s и результат записывает в d (конец строки сохраняется)
strncat(d,s,n) - Добавить в конец строки d первые n символов из строки s
strcmp(d,s) - сравнивает две строки, если они равны, то возвращает 0, если d<s, то возвращает число <0, иначе число >0
char c = 'B';
u = strchr(s, c);// Результатам выполнения функции strchr() будет адрес первого символа в строке s, который равен искомому символу c. Если символ не найден, то в указатель u будет записано число 0.
u = strrchr(s, c);//Вычисляется адрес последнего вхождения символа c в строку s (т.е. справа или с конца строки).
u=strstr(d,s) - поиск строки d в строке s; возвращает адрес на начало подстроки, если строка найдена, иначе NULL
С++:
При работе со строками обычно используют функции библиотеки string.h:
l=a.size(); - длина строки
l=a.length();
a.insert(index,"const"); - вставка подстроки "const" в строку a с позиции index
string b("moroz"); - инициализация строки
a="oй, "+b+", "+b+"!"; - конкатенация (слияние) двух строк
a.replace(index,count,b); - замена count символов на подстроку, начиная с позиции index
b=a.substr(index, count); - выделение подстроки длиной count из строки а, начиная с позиции index
//удаление подстроки "ok"
int n;
while((n=a.find("ok"))!=-1) //пока символ есть
{
a.erase(n,2);//удаляем с позиции n два символа
}
a.swap(b); - обмен строк
Более подробно смотрите о
Си и
С++.
