Выведите все точные квадраты натуральных чисел, не превосходящие данного числа n. формат входных данных задано единственное число n. формат выходных данных необходимо вывести все точные квадраты натуральных чисел, не превосходящие данного числа n.
Наивный алгоритм: используя два вложенных цикла, проверить все подстроки, являются ли они палиндромами. Такой алгоритм будет работать O(|S|^2), что при ограничении |S| <= 10^5 потребует примерно 10^10 / 2 сравнений, что достаточно долго.
Оптимизация: в центре у палиндрома четной длины всегда пара одинаковых символов. Их можно найти, а затем увеличивать длину до тех пор, пока это возможно. Плюс этого наблюдения в том, что если пара попадется не в центре, то максимальная длина подстроки-палиндрома с центром в этой паре, будет ограничена сверху. Однако в худшем случае (все символы одинаковы) всё равно придется произвести немалое число сравнений.
Однако задачу можно решить и за линейное время. Например, существует алгоритм Манакера, основанный на том, что можно использовать информацию, что часть строки является палиндромом. А именно, если в длинную-длинную строку-палиндром входит другая подстрока-палиндром, то можно не начинать проверку заново, а использовать уже имеющуюся информацию.
Пример 1: "длинная" подстрока-палиндром: cbbaabbaabbc в которой известна подстрока-палиндром. Тогда в строке есть симметричная подстрока-палиндром: cbbaabbaabbc Пример 2: "длинная" подстрока палиндром: bbaabbaabbaa Зная, что в ней есть подстрока-палиндром bbaabbaabbaa, можно явные сравнения для подстроки с центром в bbaabbaabbaa начинать уже с bbaabbaabbaa
Если не хочется писать самостоятельно, алгоритм Манакера легко находится.
1. У файлі зберігається блок інформації. 2. Від програми в якому він створюється, редагується, зберігається.ї 3. Дозволяється використовувати до 255 символів.Дозволяється використовувати символи національних алфавітів, зокрема російського.Дозволяється використовувати пробіли та інші раніше заборонені символи, за винятком наступних дев'яти: / \ :*?"|.В імені файлу можна використовувати кілька точок. Розширенням імені вважаються всі символи, які стоять за останньою крапкою. 4. Для зручності і сортування.
var
i,n:integer;
begin
readln(n);
for i:=1 to n-1 do write(i*i:5);
end.