Уазизхана есть строка s. его интересует сколько есть подстрок четной длины у строки s, которые являются палиндромами. одинаковые подстроки начинающие с разных позиций считаются разными. формат входных данных единственная строка входного файла содержит одну строку s состоящее из строчных букв алфавита (1 < = длина s < = 100000). формат выходных данных выведите ответ к .

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

Основное действие оставил функцией, так как проще потом осуществлять вызов в зависимости от того, какой массив больше

ответ (вариант исполнения 1):

#include <iostream>

using namespace std;

bool IsInclude(int* Find, int* Suorce, int sizeFind, int sizeSuorce);

int main()

{

int *A, *B, NA, NB;

setlocale(LC_ALL, "rus");

bool result;

cout << "Введите количество элементов первого массива: ";

cin >> NA;

A = new int[NA];

cout << "Введите элементы массива: " << endl;;

for (int i = 0; i < NA; i++) { cout << "A["<< i << "] = "; cin >> A[i]; }

cout << "Введите количество элементов второго массива: ";

cin >> NB;  

B = new int[NB];

cout << "Введите элементы массива: " << endl;;

for (int i = 0; i < NB; i++) { cout << "B[" << i << "] = "; cin >> B[i]; }

//Тепеь смотрим какой массив длиннее и в зависимости от этого запускаем функцию по разному

if (NA > NB)

{

 result = IsInclude(B, A, NB, NA);

 if (result) cout << "Массив B входит в массив A";

 else cout << "Массив B не входит в массив A";

}

else {

 result = IsInclude(A, B, NA, NB);

 if (result) cout << "Массив A входит в массив B";

 else cout << "Массив A не входит в массив B";

}

delete[] A;

delete[] B;

return 0;

}

bool IsInclude(int* Find, int* Suorce, int sizeFind , int sizeSuorce)

{

int CountInSuorce, CountInFind;

for (int i = 0; i < sizeFind; i++) { // Перебираем по одному все элементы меньшего массива  

 CountInSuorce = 0;

 CountInFind = 0;

 for (int j = 0; j < sizeSuorce; j++)

 {

  if (Find[i] == Find[j] && j < sizeFind) CountInFind++; // Считаем сколько раз элемент искомого массива находится в нём самом

  if (Find[i] == Suorce[j]) CountInSuorce++; // Считаем сколько раз элемент искомого массива встретился в большем массиве

 }

 if (CountInFind > CountInSuorce) return false;// Если счётчик элементов в искомом массиве оказался больше чем в большем массиве, значит выходим и дальше не имеет смысла искать

}

return true;// Если счётчики большего массива были всегда не меньше счетчика искомого массива, то мы попадём сюда и меньший массив можно составить из элементов большего

}

ответ (вариант исполнения 2):

#include <iostream>

using namespace std;

int IsInclude(int* First, int FirstCount, int* Second, int SecondCount);

int main()

{

int* A, * B, NA, NB;

setlocale(LC_ALL, "rus");

int result;

cout << "Введите количество элементов первого массива: ";

cin >> NA;

A = new int[NA];

cout << "Введите элементы массива: " << endl;;

for (int i = 0; i < NA; i++) { cout << "A[" << i << "] = "; cin >> A[i]; }

cout << "Введите количество элементов второго массива: ";

cin >> NB;

B = new int[NB];

cout << "Введите элементы массива: " << endl;

for (int i = 0; i < NB; i++) { cout << "B[" << i << "] = "; cin >> B[i]; }

result = IsInclude(A, NA, B, NB);

switch (result) {

 case 0: {cout << "Массивы A и B не входят друг в друга"; break; }

 case 1: {cout << "Массивы A и B имеют одинаковые элементы"; break; }

 case 2: {cout << "Массив A входит в массив B"; break; }

 case 3: {cout << "Массив B входит в массив A"; break; }

}

delete[] A;

delete[] B;

return 0;

}

int IsInclude(int* First, int FirstCount, int* Second, int SecondCount) // возвращаем 0 если массив не входид в другой, 1 если они одинаковые, 2 если первый входит во второй, 3 если второй входит в первый

{

int *Source, * Find, sizeSource, sizeFind, CountInSource, CountInFind;

bool Equal; // Флаг того что элементы одинаковые

bool AandB = FirstCount > SecondCount;

if(AandB)

{

 Source = First;

 sizeSource = FirstCount;

 Find = Second;

 sizeFind = SecondCount;

}

else  

{

 Find = First;

 sizeFind = FirstCount;

 Source = Second;

 sizeSource = SecondCount;

}

if (sizeFind == sizeSource) Equal = true;

else Equal = false;

for (int i = 0; i < sizeFind; i++) { // Перебираем по одному все элементы меньшего массива  

 CountInSource = 0;

 CountInFind = 0;

 for (int j = 0; j < sizeSource; j++)

 {

  if (Find[i] == Find[j] && j < sizeFind) CountInFind++; // Считаем сколько раз элемент искомого массива находится в нём самом

  if (Find[i] == Source[j]) CountInSource++; // Считаем сколько раз элемент искомого массива встретился в большем массиве

 }

 if (CountInFind > CountInSource) return 0;// Если счётчик элементов в искомом массиве оказался больше чем в большем массиве, значит выходим и дальше не имеет смысла искать

 if (CountInFind != CountInSource) Equal = false; // Если количество в искомом и большом получилось различное, то сбрасываем флаг

}

// Если счётчики большего массива были всегда не меньше счетчика искомого массива, то мы попадём сюда и меньший массив можно составить из элементов большего

if (Equal) return 1; // если флаг не сброшен, то возврвщаем 1

if (!Equal && AandB) return 3; // если флаг не сброшен, то возврвщаем 1

else return 2;

}