|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
24.12.2013, 09:58 | #1 |
Пользователь
Регистрация: 25.02.2013
Сообщений: 57
|
Задана строка A(N). Вычислить для каждой подстроки функцию A(i), равную палиндрому максимальной длины
Привет всем! Скажите что от меня требуют в этой задачи? Я условие не понял)))
Дана строка S, состоящая из N символов. Определим функцию A(i) от первых i символов этой сроки следующим образом: A(i) = максимально возможному k, что равны следующие строки: S[1]+S[2]+S[3]+…+S[k] S[i]+S[i–1]+S[i–2]+…+S[i–k+1] где S[i] – i-ый символ строки S, а знак + означает, что символы записываются в строчку непосредственно друг за другом. Напишите программу, которая вычислит значения функции A для заданной строчки для всех возможных значений i от 1 до N. Формат входных данных В первой строке входного файла записано одно число N. 1<=N<=200000. Во второй строке записана строка длиной N символов, состоящая только из больших и/или маленьких латинских букв. Формат выходных данных В выходной файл выведите N чисел — значения функции A(1), A(2), … A(N). Пример h.in 5 aabaa h.out 1 2 0 1 5 Последний раз редактировалось forged; 24.12.2013 в 10:07. |
24.12.2013, 10:57 | #2 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
по поводу A(i) поясню:
для заданного I берём из строки подстроку с 1-го символа и до I-го включительно. в этой подстроке ищём максимальное значение, для которого строка слева направа и справа налево является одинаковой. например, для строки из вашего примера, при i=2 мы получаем подстроку aa k = 0; читаем её слева направо: a и справа налево: a (уже k +1) дальше, продолжаем читать слева направо: aa и справа налево: aa (уже k+1) всё. строка закончилась, A(2) = 2 теперь возьмём i=3 Получаем подстроку aab k = 0; берём символ слева направо: a и справо налево, получаем символ b они не равны - всё, прервали вычисление, A(3) = 0 для i=5 получаем подстроку aabaa (то, что она совпадает со строкой, это просто следствие того, что i равно N) предлагаю Вам вычислить сколько максимально символов строки взятые слева направо, равны символам, взятым из этой же подстроки справа налево.... Теперь стало понятней? |
24.12.2013, 11:30 | #3 |
Пользователь
Регистрация: 25.02.2013
Сообщений: 57
|
Что-то не до конца
|
24.12.2013, 12:56 | #4 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Делфи.Написать функцию нахождения максимальной длины подпоследовательности значений массива,которые идут подряд и не увеличиваются | Jane_Air | Помощь студентам | 1 | 03.11.2013 11:54 |
поиск последовательности элементов максимальной длины в массиве | Alkcatras | Visual C++ | 0 | 05.01.2013 18:43 |
Задача со строкой (поиск слова максимальной длины) | TheAlina | Помощь студентам | 1 | 13.05.2012 23:34 |
Слово максимальной длины | Broken Angel | Помощь студентам | 2 | 06.01.2011 15:14 |
Палиндром максимальной длины (язык Pelles C) | Kotik Wasil | Помощь студентам | 2 | 13.12.2010 11:32 |