Pagini recente » Cod sursa (job #1572579) | Cod sursa (job #20066) | Cod sursa (job #832776) | Cod sursa (job #440079) | Cod sursa (job #2008795)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
const int nMax = 2000005;
void Manacher(char v[], int sz, int ret[])
{
ret[0] = 0;
int st, dr;
for(int i = 1; i < sz-1; ++i)
{
if(v[i-1] == v[i+1])
{
st = i - ret[i-1];
dr = i + ret[i-1];
ret[i] = ret[i-1] - 1;
while(st >= 0 && dr < sz && v[st--] == v[dr++])
ret[i]++;
}
else
ret[i] = 0;
}
ret[sz-1] = 0;
}
int n;
char a[nMax];
char t[nMax];
int pal[nMax];
int main()
{
ifstream in("pscpld.in");
in >> t;
in.close();
n = strlen(t);
char add[3];
add[1] = '#';
add[2] = '\0';
for(int i = 0; i < n; ++i)
{
add[0] = t[i];
strcat(a, add);
}
n = strlen(a) - 1;
Manacher(a, n, pal);
int rasp = 0;
for(int i = 0; i < n; i += 2)
rasp += (pal[i] / 2) + 1;
for(int i = 1; i < n; i += 2)
rasp += (pal[i] / 2);
ofstream out("pscpld.out");
out << rasp;
out.close();
return 0;
}