Написать рекурсивную программу, которая: вычисляет произведение p(n) = 2 x 4 x 6 2n.

#include< iostream> using namespace std; int d(int); int main() { cout< < ""; int i; cin> > i; cout< < d(i*2)< < endl; system("pause"); return 0; } int d(int n) { if(n==2) return 2; else return d(n)*d(n-2); }

Наивный алгоритм: используя два вложенных цикла, проверить все подстроки, являются ли они палиндромами. такой алгоритм будет работать o(|s|^2), что при ограничении |s| < = 10^5 потребует примерно 10^10 / 2 сравнений, что достаточно долго. оптимизация: в центре у палиндрома четной длины всегда пара одинаковых символов. их можно найти, а затем увеличивать длину до тех пор, пока это возможно. плюс этого наблюдения в том, что если пара попадется не в центре, то максимальная длина подстроки-палиндрома с центром в этой паре, будет ограничена сверху. однако в худшем случае (все символы одинаковы) всё равно придется произвести немалое число сравнений. однако можно решить и за линейное время. например, существует алгоритм манакера, основанный на том, что можно использовать информацию, что часть строки является палиндромом. а именно, если в длинную-длинную строку-палиндром входит другая подстрока-палиндром, то можно не начинать проверку заново, а использовать уже имеющуюся информацию. пример 1: "длинная" подстрока-палиндром: c bbaabbaabbc в которой известна подстрока-палиндром. тогда в строке есть симметричная подстрока-палиндром: cbbaa bbaabbc пример 2: "длинная" подстрока палиндром: bbaabbaabbaa зная, что в ней есть подстрока-палиндром bbaabbaabbaa, можно явные сравнения для подстроки с центром в bbaabb aabbaa начинать уже с  bbaa bbaabbaa если не хочется писать самостоятельно, алгоритм манакера легко находится.