Упражнения. 1. На основании приведенных в лекции функций реализуйте алгоритмы поиска подстроки в строке

1. На основании приведенных в лекции функций реализуйте алгоритмы поиска подстроки в строке.

2. Строка S была записана много раз подряд, после чего из получившейся строки взяли подстроку и передали как входные данные. Необходимо определить минимально возможную длину исходной строки S.

Формат входных данных

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

Формат выходных данных

В выходной файл нужно вывести одно число – ответ на задачу.

Пример входного файла input.txt

abababa

Пример выходного файла output.txt

3. Даны две строки a и b. Требуется найти максимальную длину префикса строки a, который входит как подстрока в строку b. При этом считать, что пустая строка является подстрокой любой строки.

Формат входных данных

В первой строке входного файла содержится строка a, во второй – строка b. Элементами строк a и b являются произвольные символы с кодами ASCII больше 32. Длина каждой строки от 1 до 30000.

Формат выходных данных

В выходной файл вывести искомую длину префикса строки a, т.е. целое число от 0 до длины строки a.

Пример входного файла input.txt

abcdefghijklmnopqrstuvwxyz

Abcd?aBcd!abCd.abcD!?

Пример выходного файла output.txt

4. Назовем строку палиндромом, если она одинаково читается слева направо и справа налево. Примеры палиндромов: «abcba», «55», «q», «xyzzyx». Требуется для заданной строки найти максимальную по длине ее подстроку, являющуюся палиндромом.

Формат входных данных

Во входном файле содержится единственная строка, состоящая из строчных букв латинского алфавита и цифр. Длина строки не превосходит 2000.

Формат выходных данных

В выходной файл выведите одно целое число - максимальную длину подстроки, являющейся палиндромом.

Пример входного файла input.txt

a123bc9e9c321

Пример выходного файла output.txt

Литература

1. Ахо А., Хопкрофт Дж., Ульман Д. Структуры данных и алгоритмы. Уч. пособие. — М.: Вильямс, 2000. – 384с.

2. Кнут Д.Э. Искусство программирования. Том 3. Сортировка и поиск, 3-е изд.: Пер. с англ.: Уч. пос. – М.: Вильямс, 2000. – 832 с.

3. Кормен Т., Леверсон Ч.., Ртвест Р. Алгоритмы. Построение и анализ. — М.: МЦНМО, 1999. – 960 с.

4. Подбельский, В.В. Программирование на языке Си: учеб. пособие / В.В. Подбельский, С.С. Фомин. – М.: Финансы и статистика, 2004. – 600 с.

5. Подбельский, В.В. Язык Си++: учеб. пособие / В.В. Подбельский. – М.: Финансы и статистика, 2005. – 560 с.

6. Сэджвик Р. Фундаментальные алгоритмы на С++. Части 1-4. Анализ, структуры данных, сортировка, поиск. — М.: Диасофт, 2001. – 687 с.

7. Хусаинов Б.С. Структуры и алгоритмы обработки данных. Примеры на языке Си. Учебное пособие. – М.: Финансы и статистика, 2004. – 464 с.

Дата добавления: 2014-01-04