Pagini recente » Cod sursa (job #1038286) | Cod sursa (job #2481616) | Cod sursa (job #1564775) | Cod sursa (job #1375533) | Cod sursa (job #908360)
Cod sursa(job #908360)
#include <fstream>
#include <cstring>
#define N 2000010
using namespace std;
string s;
int Pal[N], L, C, R, n, i, j;
long long k;
int main()
{
ifstream fi("pscpld.in");
ofstream fo("pscpld.out");
fi >> s;
n = s.length();
n += n-1;
C = R = 0;
for(i = 1; i < n; i++)
if(R <= i)
{
L = C = R = i;
if(i%2 == 1)
{
R++;
L--;
}
while(L >= 0 and R < N and s[L/2] == s[R/2])
L -= 2, R += 2;
L += 2; R -= 2;
if(s[L/2] != s[R/2]) L = R = i;
C = i; Pal[i] = (R - C + 1)/2;
if(i%2 == 0) Pal[i]++;
}
else
{
j = 2*C - i;
if(Pal[j] < ((R - i + 1)/2))
{
Pal[i] = Pal[j];
continue;
}
C = i;
L = 2*C - R;
while(L >= 0 and R < N and s[L/2] == s[R/2]) L -= 2, R += 2;
L += 2; R -= 2;
Pal[i] = (R - C + 1)/2;
if(i%2 == 0) Pal[i]++;
}
for(i = 1, k = 1; i < n; i++) k += (long long)Pal[i];
fo << k << "\n";
return 0;
}