Pagini recente » Cod sursa (job #633069) | Cod sursa (job #128956) | Cod sursa (job #1048646) | Cod sursa (job #147254) | Cod sursa (job #2068860)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
const int NMax = 1000005;
char s[NMax];
int lp[2*NMax-5];
void Manacher()
{
int C = 1;
int R = 2;
int iMirror;
int N = strlen(s);
N = 2 * N + 1;
lp[0] = 0;
lp[1] = 1;
for(int i=2; i < N; ++i)
{
iMirror = 2 * C - i;
lp[i] = 0;
int diff = R - i;
if(diff > 0)
{
lp[i] = min(lp[iMirror], diff);
}
while (((i + lp[i]) < N && (i - lp[i]) > 0) &&
(((i + lp[i] + 1) % 2 == 0) ||
(s[(i + lp[i] + 1)/2] == s[(i - lp[i] - 1)/2] )))
{
lp[i]++;
}
if(i + lp[i] > R)
{
C = i;
R = i + lp[i];
}
}
}
int main()
{
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
fin >> s;
Manacher();
long long sum = 0;
int N = strlen(s);
N = 2*N + 1;
for(int i=1; i<N; ++i)
{
if(lp[i]%2 == 1)
sum += lp[i]/2 + 1;
else
sum += lp[i]/2;
}
fout << sum;
return 0;
}