Pagini recente » Cod sursa (job #200665) | Cod sursa (job #583624) | Cod sursa (job #720834) | Cod sursa (job #2004978) | Cod sursa (job #3209746)
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin ("pscpld.in");
ofstream cout ("pscpld.out");
int lungime_palindrom[2000002];
char sir[2000002];
int main ()
{
cin >> sir;
int lungime = strlen(sir);
for (int indice_1 = lungime - 1 , indice_2 = ((lungime <<= 1)++) ; indice_1 >= 0 ; indice_1-- , indice_2 -= 2)
{ sir[indice_2] = '|'; sir[indice_2 - 1] = sir[indice_1]; }
sir[0] = '|';
for (int centru = 0 , lungime_actuala = 0 ; centru < lungime ; )
{
while (lungime_actuala <= centru && centru + lungime_actuala < lungime && sir[centru - lungime_actuala] == sir[centru + lungime_actuala])
{ lungime_actuala++; }
lungime_palindrom[centru] = lungime_actuala; lungime_actuala = 0;
for (int initial = centru++ , stanga = initial - 1 ; centru < initial + lungime_palindrom[initial] ; stanga-- , centru++) {
if (stanga - lungime_palindrom[stanga] > initial - lungime_palindrom[initial])
{ lungime_palindrom[centru] = lungime_palindrom[stanga]; }
else
if (stanga - lungime_palindrom[stanga] < initial - lungime_palindrom[initial])
{ lungime_palindrom[centru] = initial + lungime_palindrom[initial] - centru; }
else
{ lungime_actuala = lungime_palindrom[stanga]; break; }
}
}
uint64_t total = 0;
for (int indice = 0 ; indice < lungime ; indice++)
{ total += (lungime_palindrom[indice] >> 1); }
cout << total;
cout.close(); cin.close();
return 0;
}