04-strings1 (1238875)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

СТРОКИC-строки. Некоторые интересные алгоритмы на строках. Основыдинамического программированияК. Владимиров, Intel, 2019mail-to: konstantin.vladimirov@gmail.comЗначения символов•То, что вы привыкли считать символами, на самом деле кодируется числамиint c = 'A';printf("%d\n", c); // что на экране?•И наоборот достаточно небольшие цифры это коды для символовchar x = 65;printf("%c\n", x); // а сейчас?•В Unix формат символов это UTF-8.

Его первые 127 символов совпадают стаблицей ASCIIУпражнение•Распечатайте символы с 0 по 127 рядами по 16•Чисто визуально на какие категории вы можете разделить эти символы?Категории символов•Специальный заголовочный файл <ctype.h> содержит прототипы функций,категоризирующих символы.•Например is_alpha(c) проверяет является ли c одним из алфавитных символов(abcdef....), а is_digit(c) проверяет на цифру. Их объединяет is_alphanum(c)•Иногда в программах которые анализируют символьную информацию важнознать что на вход пришло "что-то вроде буквы" или "что-то вроде пробела"•На следующей картинке сведены основные определители из ctypeКатегории символовИсточник: https://en.cppreference.com/w/c/string/byte/isspaceDisclaimer: мы не нырнём глубоко•Далее мы работаем только с ASCII строками то есть со строками, состоящимииз однобайтных символов UTF8•Учёт различных кодировок, русских букв, китайских иероглифов и всеготакого просто не входит в программу первого курса•Приветствуется если любознательная часть аудитории что-нибудь почитаетсамостоятельноСтроковые литералы•Следующая строчка может показаться смутно знакомойprintf("%s\n", "Hello, world!");•Символы "Hello, world" в кавычках это строковый литералH ello,w o rld! \0•Строковый литерал это строка известная во время компиляции•Любая строка в языке C оканчивается завершающим нулевым символом•Нулевой символ '\0' это не символ '0'.

Это спецсимвол, имеющий код 0.Изменяемые строки•Самый простой способ создать изменяемую строку это объявить массивсимволовchar hello[20] = "Hello, world!";•Символы после завершающего нуля (он тут 14-й) содержат мусор•Далее содержимое этой строки можно поменятьhello[1] = 'a';printf("%s\n", hello); // → Hallo, world!•Изменяемая строка это любой массив символов, завершающийся нулём•Символы после завершающего нуля ничего не значатC-строки и разные виды памяти•Обычно используют указатель на первый элементchar const * cinv = "Hello, world";0xa000He.........d!\0cinvcmutHe.........d!\0He.........d!\0char cmut[] = "Hello, world";char *cheap = (char *) malloc (50);strcpy (cheap, cinv);cheap = cinv;cheapcinv = 0;cmut = cheap;0xb000C-строки и разные виды памяти•Обычно используют указатель на первый элементchar const * cinv = "Hello, world";0xa000He.........d!\0cinvcmutHe.........d!\0He.........d!\0char cmut[] = "Hello, world";char *cheap = (char *) malloc (50);strcpy (cheap, cinv);cheap = cinv; // ошибка компиляции+ утечка памятиcheapcinv = 0; // okcmut = cheap; // ошибка компиляции0xb000Problem SCN – суммирование в строке•Ваша задача написать программу которая суммирует строчку, воспринимаясимволы в ней как коды этих символовH e#72•llo#101 #108 #108 #111,#44w o r#32ld#119 #111 #114 #108 #100Для "Hello, world!" ответом будет 1161! \0#33#0Копирование строк•Одна строка может быть скопирована в другуюchar hello[20] = "Hello, world!";char duplicate[20];char const * src = hello;char * dst = duplicate;while (*src != '\0') {*dst = *src; dst += 1; src += 1;}*dst = '\0';•Все ли понимают что происходит в этом коде?Копирование строк•Одна строка может быть скопирована в другуюchar hello[20] = "Hello, world!";char duplicate[20];char const * src = hello;char * dst = duplicate;while ((*dst++ = *src++) != '\0') {} // немного джигитовкиКопирование строк•Одна строка может быть скопирована в другуюchar hello[20] = "Hello, world!";char duplicate[20];strcpy (duplicate, hello); // используем библиотечную функцию•Вашим выбором по умолчанию должно быть именно использованиебиблиотечных функций, так как они почти всегда корректны и куда лучшеоптимизированы•В языке C довольно много библиотечных функций для работы со строкамиAPI для работы с C-строкамиБиблиотечная функцияЧто она делаетstrcpy(dest, src)Копирует src в deststrcat(dest, src)Дописывает src в конец deststrlen(src)Вычисляет длину srcstrcmp(src1, src2)Сравнивает src1 и src2.

Возвращает 0, 1 или -1strchr(src, c)Ищет символ в строкеstrstr(haystack, needle)Ищет подстроку в строкеstrspn(src1, src2)Ищет максимальный префикс src1 состоящий только изсимволов src2strcspn(src1, src2)Тоже только не из символов src2strpbrk(src1, src2)Ищет первое вхождение в src1 любого символа из src2Обсуждение•Одна забавная странность в сигнатурах стандартной библиотекизаключается в том, что возвращаемый тип почти всегда char*char *strstr(const char *s1, const char *s2);•Казалось бы, если мы принимаем оба аргумента const char* почему бы невозвращать const char*•У кого есть идеи почему так сделано?Problem SR – переворот подстрок•Напишите программу, которая берёт одно слово, а потом некоторый текст ипереворачивает в этом тексте все вхождения этого слова•Например для слова "world" и текста "Hello, world!" результатомдолжно быть "Hello, dlrow!"•Вы можете предполагать что текст состоит из слов, разделённых пробелами ипунктуацией, а слово состоит из алфавитных символов•Вы также можете использовать любые функции стандартной библиотеки,включая strstr для поиска подстрокиКонкатенация строк•Рассмотрим пристальней функцию strcatchar buf[20] = "Hello";strcat(buf, ", world!"); // → "Hello, world!"•Как она могла бы работать?Конкатенация строк•Рассмотрим пристальней функцию strcatchar buf[20] = "Hello";strcat(buf, ", world!"); // → "Hello, world!"•Как она могла бы работать?•Единственный алгоритм: дойти до конца строки-приёмника, а потом поодному добавлять символы из строки-источника•При этом мы тратим ( + ) времениПроблема Шлемиля-маляра•Следующий код довольно плохchar buf[MAXSZ];strcpy(buf, "First ");strcat(buf, "Second ");strcat(buf, "Third ");strcat(buf, "Fourth ");•Что здесь не так? Как бы вы переписали этот код?Обсуждение•Ещё одной проблемой strcat (кроме обсуждённых ранее проблем сасимптотикой) является возможное переполнение буфера•Допустим у нас строки живут только в динамической памяти•Можем ли мы тогда написать strcat которая увеличивает буфер, если его нехватает? Как она могла бы работать?Реаллокации•Чтобы немного расширить буфер в динамической памяти, делать malloc нановый размер и free на старом месте может быть накладно•Здесь на помощь приходит reallocvoid * realloc(void * ptr, size_t new_size);•Напримерint * arr = (int *) malloc(100);arr = (int *) realloc(arr, 1000);•При нехватке памяти, realloc возвращает NULL•Внимание: realloc не работает на стеке и в глобальной памятиProblem SA – concat + realloc•Ваша задача написать функциюchar *strcat_r(char *dest, int bufsz, const char *src);•При нехватке места в старом буфере эта функция должна реаллоцироватьпамять и возвращать новый указатель•Будьте очень внимательны с нулевым символомProblem SP – замена в строке•Реализуйте функцию, осуществляющую замену всех подстрок в строке•Функция должна вернуть новую строку, аллоцированную в кучеchar * replace(char *str, char const *from, char const *to);•Напримерchar *s = (char *) malloc(41);strcpy(s, "Hello, %username, how are you, %username");char *r = replace(s, "%username", "Eric, the Blood Axe");•Обратите внимание, что строка from может быть и длиннее и короче чем toАргументы функции main•До сих пор мы пользовались main() или main(void)•Но есть вторая форма основной функцииint main(int argc, char **argv) {// тело функции}•argc это количество аргументов•argv это массив argc+1 строк•argv[0] это имя самой программыProblem EA – вывести аргументы main•Напишите программу которая будет печатать аргументы с которыми вызвана,заменяя '-' на '+'> ./a.out -a t -x --b 123-a t +x ++b 123•Если среди этих аргументов есть -r, программа должна вывести их вобратном порядке> ./a.out -a t -r -x --b 123123 ++b +x +r t +a•Как вы думаете почему именно '-' является стандартным для аргументовкомандной строки?Problem SU – поиск CI подстроки•Напишите простую функцию strstrci, которая ищет подстроку в строке, независимо отрегистра символов (ci означает case insensitive)char * strstrci(char const * needle, char const * haystack);•Ниже приведён пример примененияchar const *needle = "Ab", *src = "abracadaBra";char *pos1, *pos2, *pos3;pos1 = strstrci(src, needle);pos2 = strstrci(pos1 + 2, needle);pos3 = strstrci(pos2 + 2, needle);assert(pos1 != NULL);assert(pos2 != NULL);assert(pos3 == NULL);•Первая найденная позиция "abracadabra", вторая "abracadaBra"•Оцените асимптотику наивного алгоритмаHWK – алгоритм КМП (optional)••Более интересный алгоритм Кнута-Морриса-Пратта делает из строкиавтомат, вычисляя так называемую failure function f[i]W[i]ABACABS[0:i]AABABAABACABACAABACABf[i]001012Далее с использованием этой табличной функции идёт поиск123ABABACABACAB•AABACABCСмотрим f[2] == 1, сдвигаем на 3 - f[2] == 2ACBCAAAHWK – алгоритм КМП (optional)••AB•Более интересный алгоритм Кнута-Морриса-Пратта делает из строкиавтомат, вычисляя так называемую failure function f[i]W[i]ABACABS[0:i]AABABAABACABACAABACABf[i]001012Далее с использованием этой табличной функции идёт поиск1234ABACAAABACABBACABCСмотрим f[3] == 0, сдвигаем на 4 - f[3] == 4ACBCAAAHWK – алгоритм КМП (optional)••Более интересный алгоритм Кнута-Морриса-Пратта делает из строкиавтомат, вычисляя так называемую failure function f[i]W[i]ABACABS[0:i]AABABAABACABACAABACABf[i]001012Далее с использованием этой табличной функции идёт поиск1ABA•BACAABACAABACABBCСмотрим f[0] == 0, сдвигаем на 1 - f[0] == 1ACBCAAAHWK – алгоритм КМП (optional)••ABБолее интересный алгоритм Кнута-Морриса-Пратта делает из строкиавтомат, вычисляя так называемую failure function f[i]W[i]ABACABS[0:i]AABABAABACABACAABACABf[i]001012Далее с использованием этой табличной функции идёт поискA•BACAmatch!ABACABABACABCACBНашли подстроку.

Дома: реализуйте этот алгоритм на языке CCAAAРасстояние редактирования•Как перейти от слова spoon к слову sponge?•Что можно делать:••••Вставлять букву в любое место (цена == 1)Удалять любую букву (цена == 1)Изменять любую букву (цена == 2)Нужно найти последовательность действий с минимальной ценойspoon → sponn (+2) → spong (+2) → sponge (+1), cost = 5spoon → spon (+1) → spong (+1) → sponge (+1), cost = 3Обсуждение•Можете ли вы предложить наивное решение для расстоянияредактирования?Обсуждение•Можете ли вы предложить наивное решение для расстоянияредактирования?•Скорее всего оно очень плохо.•Для такого рода задач обычно используется дискретное динамическоепрограммированиеПринцип Беллмана•«An optimal policy has the property that whatever the initial state and initialdecision are, the remaining decisions must constitute an optimal policy withregard to the state resulting from the first decision» •Изменение состояния: → +1 = ( , ) with pay-off ( , )•Обозначим 0 = max σ ( , )•Тогда = max , + , •Простыми словам: любой кусок оптимальной траектории являетсяоптимальной траекторией0...

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций