Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Delphi программирование > Паскаль, Turbo Pascal, PascalABC.NET
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Внимание! Есть замечания модератора по теме: исправил название, чтобы оно отражало суть решаемой задачи!
Старый 24.12.2013, 09:58   #1
forged
Пользователь
 
Регистрация: 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.
forged вне форума Ответить с цитированием
Старый 24.12.2013, 10:57   #2
Serge_Bliznykov
Старожил
 
Регистрация: 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)
предлагаю Вам вычислить сколько максимально символов строки взятые слева направо, равны символам, взятым из этой же подстроки справа налево....

Теперь стало понятней?
Serge_Bliznykov вне форума Ответить с цитированием
Старый 24.12.2013, 11:30   #3
forged
Пользователь
 
Регистрация: 25.02.2013
Сообщений: 57
По умолчанию

Что-то не до конца
forged вне форума Ответить с цитированием
Старый 24.12.2013, 12:56   #4
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,229
По умолчанию

Цитата:
Сообщение от forged Посмотреть сообщение
Что-то не до конца
так. до какого именно конца не понимаете?!

Допустим, есть строка a11a23
попытайтесь найти
A(3)
или
A(4)

пошагово, (так, как я расписывал или даже подробнее). Вот мы и увидим, на каком месте у вас остались "непонятки"...
Serge_Bliznykov вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Делфи.Написать функцию нахождения максимальной длины подпоследовательности значений массива,которые идут подряд и не увеличиваются 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