Короткие примеры C++ кода-1 Кувшинов Д

nullptr

};
if (!are_equal(words, long_reference))

return 5;
return 0; // ошибки не обнаружены.

}

#include

int main()

{

const auto test = test_split();

std::cout << test << std::endl;

assert(test == 0);

return EXIT_SUCCESS;

}

0565-login.c

// login.c

// Пример уязвимости gets и printf.

// Имел параллели в реальном коде.

#include

#include

#include

#include

// Сгенерировать псевдослучайную строку.

void generate_random_str(char *str, size_t n)

{

memset(str, 0, n + 1);

while (n--)

str[n] = 'a' + rand() % 26;

}

// Сгенерировать псевдослучайные логин и пароль.

void load_credentials(char **login, char **pwd)

{

static char login_buf[9];

static char pwd_buf[9];
generate_random_str(login_buf, 8);

generate_random_str(pwd_buf, 8);
*login = login_buf;

*pwd = pwd_buf;

}

int main(void)

{

#define BUFSIZE 80

char login_buf[BUFSIZE];

char pwd_buf[BUFSIZE];



char *root_login;

char *root_pwd;
// Сгенерировать случайные логин и пароль.

srand(time(NULL));

load_credentials(&root_login, &root_pwd);
// Допускается бесконечное число попыток входа.

for (;;)

{

// Считать логин.

memset(login_buf, 0, BUFSIZE);

memset(pwd_buf, 0, BUFSIZE);

printf("Login:");

gets(login_buf);
// Считать пароль.

printf("Pwd:");

gets(pwd_buf);



// Сравнить логин и пароль со сгенерированными.

if (strcmp(login_buf, root_login) || strcmp(pwd_buf, root_pwd))

{

printf(login_buf);

printf(" failed to login\n");

}

else // access granted

{

printf("Congratulations! Access granted!\n");

break;

}

}
getchar(); // задержка экрана

}

0570-longest_palindromic_substring_a.cpp

// longest_palindromic_substring_a.cpp

// Задача: в заданной строке найти самую длинную подстроку-палиндром.

// Алгоритм решения: начиная с длины строки (и уменьшая её до 2) перебирать все подстроки заданной длины,

// проверяя, являются ли они палиндромами.

#include
/// Функция проверяет, является ли содержимое диапазона строки палиндромом.

bool is_palindrome(const char *begin, const char *end)

{

while (begin < end)

if (*begin++ != *--end)

return false;
return true;

}
/// Найти самую длинную подстроку-палиндром в диапазоне строки.

/// Возвращает длину найденной подстроки, по указателю found записывает указатель на начало найденной подстроки.

std::size_t longest_palindrome(const char *begin, const char *end, const char **found)

{

for (auto n = end - begin; n > 1; --n) // длина палиндрома

{

for (auto pos = begin; end - pos >= n; ++pos) // начало подстроки

{

if (is_palindrome(pos, pos + n)) // палиндром?

{

*found = pos;

return n;

}

}

}
return 0;

}

///////////////////////////////////////////////////////////////////////////////

// Тестирование

#include

#include

#include

using namespace std;
/// В заданном объекте std::string найти самую длинную подстроку-палиндром

/// и вернуть её в виде нового объекта std::string.

string longest_palindrome(const string &text)

{

const char *pos = nullptr;

const auto len = longest_palindrome(text.data(), text.data() + text.size(), &pos);

return string(pos, pos + len);

}
/// Проверка результата для тестовых строк.

int test_longest_palindrome()

{

if (longest_palindrome("this isn't a text with no palindromic substrings") != "t a t")

return 1;

if (longest_palindrome("there is no word redivider in English") != " redivider ")

return 2;

if (longest_palindrome("who knows what \"detartrated\" means?") != " \"detartrated\" ")

return 3;

if (longest_palindrome("saippuakalasalakauppias is longer than"

"saippuakivikauppias but what about"

"kuulilennuteetunneliluuk?") != "kuulilennuteetunneliluuk")

return 4;

if (longest_palindrome("blast") != "")

return 5;

return 0;

}
int main()

{

auto test = test_longest_palindrome();

cout << test << endl;

assert(test == 0);

return EXIT_SUCCESS;

}

0580-longest_palindromic_substring_b.cpp

// longest_palindromic_substring_b.cpp

// Задача: в заданной строке найти самую длинную подстроку-палиндром.

// Алгоритм решения

// Искать набольшую общую подстроку двух строк: исходной и исходной в обратном порядке.

#include
/// Найти совпадающие символы при движении по диапазону 1 в прямом направлении, а по диапазону 2 -- в обратном.

/// Возвращает истину, если удалось найти.

bool find_factor

(

const char *begin1, const char *end1, // диапазон 1

const char *begin2, const char *end2, // диапазон 2

const char **found1, // позиция найденного символа в диапазоне 1

const char **found2 // позиция найденного символа в диапазоне 2

)

{

while (begin1 != end1 && begin2 != end2)

{

if (*begin1++ == *--end2)

{

*found1 = begin1 - 1;

*found2 = end2;

return true;

}

}
return false;

}
/// Посчитать длину максимальной совпадающей последовательности с начала диапазона 1 и конца диапазона 2.

std::size_t longest_common_prefix_suffix

(

const char *begin1, const char *end1, // диапазон 1

const char *begin2, const char *end2 // диапазон 2

)

{

std::size_t cnt = 0;

while (begin1 != end1 && begin2 != end2)

{

if (*begin1++ != *--end2)

break;

++cnt;

}
return cnt;

}

/// Идти по диапазону 1 с начала, а по диапазону 2 -- с конца.

/// В случае совпадающей последовательности символов считать их и вернуть самую длинную последовательность (указатель в диапазоне 1).

std::size_t longest_common_factor_0

(

const char *begin1, const char *end1, // диапазон 1

const char *begin2, const char *end2, // диапазон 2

const char **found1 // позиция найденной подстроки в диапазоне 1

)

{

std::size_t cur_max = 0;

while (find_factor(begin1, end1, begin2, end2, &begin1, &end2))

{

if (end1 <= begin1 + cur_max || ++end2 <= begin2 + cur_max)

break;
// Первый символ уже проверен find_factor, отсюда отступы на единицы.

const auto factor_len = 1 + longest_common_prefix_suffix(begin1 + 1, end1, begin2, end2 - 1);

if (cur_max < factor_len)

{

*found1 = begin1;

cur_max = factor_len;

}
begin1 += factor_len;

end2 -= factor_len;

}
return cur_max;

}

/// Перебирать все подстроки диапазона 1, сохраняя максимум результата longest_common_factor.

std::size_t longest_common_factor_1

(

const char *begin1, const char *end1, // диапазон 1

const char *begin2, const char *end2, // диапазон 2

const char **found1 // позиция найденной подстроки в диапазоне 1

)

{

std::size_t cur_max = 0;

for (; begin1 + cur_max < end1; ++begin1)

{

const char *factor_pos;

const auto factor_len = longest_common_factor_0(begin1, end1, begin2, end2, &factor_pos);

if (cur_max < factor_len)

{

cur_max = factor_len;

*found1 = factor_pos;

}

}
return cur_max;

}
/// Перебирать все подстроки диапазона 2, сохраняя максимум результата longest_common_factor.

std::size_t longest_common_factor_2

(

const char *begin1, const char *end1, // диапазон 1

const char *begin2, const char *end2, // диапазон 2

const char **found1 // позиция найденной подстроки в диапазоне 1

)

{

std::size_t cur_max = 0;

for (; begin2 + cur_max < end2; --end2)

{

const char *factor_pos;

const auto factor_len = longest_common_factor_0(begin1, end1, begin2, end2, &factor_pos);

if (cur_max < factor_len)

{

cur_max = factor_len;

*found1 = factor_pos;

}

}
return cur_max;

}

/// Найти самую длинную подстроку-палиндром в диапазоне строки.

/// Возвращает длину найденной подстроки, по указателю found записывает указатель на начало найденной подстроки.

std::size_t longest_palindrome(const char *begin, const char *end, const char **found)

{

const char *f1, *f2;

const auto

l1 = longest_common_factor_1(begin, end, begin, end, &f1),

l2 = longest_common_factor_2(begin, end, begin, end, &f2);
if (l1 == 1 && l2 == 1)

return 0;
if (l2 < l1)

{

*found = f1;

return l1;

}

else

{

*found = f2;

return l2;

}

}

///////////////////////////////////////////////////////////////////////////////

// Тестирование

#include

#include

#include

using namespace std;
/// В заданном объекте std::string найти самую длинную подстроку-палиндром

/// и вернуть её в виде нового объекта std::string.

string longest_palindrome(const string &text)

{

const char *pos = nullptr;

const auto len = longest_palindrome(text.data(), text.data() + text.size(), &pos);