06 травня 2011року

Алгоритми для роботи з рядками

Перестановка слів

   Поменяйте в строке имя и фамилию человека.

Технічні умови

   Вхідні дані

   Вхідний файл містить один рядок, у якому записані прізвище та ім'я людини (відокремлені  рівно одним пропуском).

   Вихідні дані

   У вихідний файл виведіть цю ж інформацію, проте спочатку ім'я, а потім прізвище, також відокремлені рівно одним пропуском.

Інформація про задачу

Ліміт часу: 0.1 секунди
Ліміт пам`яті: 64 MB
Бали за пройдений тест: 10
Складність: 1% 81/82

Приклад

Pupkin Vasya

Vasya Pupkin

Довгий корінь

   Для заданого натурального числа А потрібно знайти найбільше число В таке, що B2 ≤ A.

Технічні умови

   Вхідні дані

   У вхідному файлі записано натуральне число A (A ≤ 10100).

   Вихідні дані

   У вихідний файл виведіть максимальне натуральне число B, квадрат якого не перевищує A. Число B слід виводити без лідируючих нулів.

Інформація про задачу

Ліміт часу: 2 секунди
Ліміт пам`яті: 64 MB
Бали за пройдений тест: 4.7619
Складність: 54% 16/35

Приклад

17

4

КМП

   Знайти всі входження рядка T у рядок S.

Технічні умови

   Вхідні дані

   У першому рядку вхідного файлу записано рядок S, у другому рядку вхідного файлу записано рядок T. Довжини рядків більші 0 і менші 50000, рядки містять лише латинські літери.

   Вихідні дані

   Виведіть номери символів, починаючи з яких рядок T входить у рядок S у порядку зростання. Як це за звичай прийнято у програмістів, нумерація символів починається з нуля.

Інформація про задачу

Ліміт часу: 2 секунди
Ліміт пам`яті: 64 MB
Бали за пройдений тест: 11.1111
Складність: 10% 36/40

Приклад

ababbababa

aba

0 5 7

Рядки

   Хлопчик Кирило написав одного разу на аркуші паперу рядочок, який складався з великих та маленьких латинських літер, а після цього пішов грати у футбол. Коли ж він повернувся, то виявив, що його друг Дмитро написав під його рядочком ще один рядочок такої ж двожини. Дмитро стверджує, що свій рядочок він отримав циклічнм зсувом рядочка Кирила на декілька кроків праворуч (циклічний зсув рядка abcde на 2 позиції праворуч дасть рядок deabc). Проте Дмитро відомий тим, що може випадково помилитись у великій кількості обчислень, тому Кирил у розгубленості - чи вірити Дмитру? Допоможіть йому! За заданими рядками виведіть мінімально можливий розмір зсуву або -1, якщо Дмитро помилився.

Технічні умови

   Вхідні дані

   Перші два рядки вхідного файлу містять рядки Кирила та Дмитра відповідно. Довжини рядків однакові, не перевищують 10000 і не рівні 0.

   Вихідні дані

   У вихідний файл виведіть єдине число - відповідь на поставлену задачу.

Інформація про задачу

Ліміт часу: 2 секунди
Ліміт пам`яті: 64 MB
Бали за пройдений тест: 11.1111
Складність: 30% 23/33

Приклад

abcde

deabc

2

Циклічний рядок

   Рядок S було записано багато разів підряд, після чого з отриманого рядка взяли підрядок і дали вам. Ваша задача визначити мінімально можливу довжину початкового рядка S.

Технічні умови

   Вхідні дані

   У першому і єдиному рядку вхідного файлу записано рядок, який містить лише латинські літери, довжина рядка не перевищує 50000 символів.

   Вихідні дані

   У вихідний файл потрібно вивести одне число - відповідь до задачі.

Інформація про задачу

Ліміт часу: 2 секунди
Ліміт пам`яті: 64 MB
Бали за пройдений тест: 11.1111
Складність: 25% 3/4

Приклад

abababa

2