Pagini recente » Cod sursa (job #573472) | Cod sursa (job #799005) | Cod sursa (job #555326) | Cod sursa (job #2780570) | Cod sursa (job #2638885)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
const int DIM = 100005;
int n,A[DIM],B[DIM];
long long ans=0;
char S[DIM];
void Read()
{
while(fin>>S[n])
n++;
}
void Manacher()
{
int l=0,r=-1;
for(int i=0;i<n;i++)
{
int k=1;
if(i<=r)
k=min(A[l+r-i],r-i+1);
while(i-k>=0 && i+k<n && S[i-k]==S[i+k])
k++;
A[i]=k;
k--;
if(i+k>r)
{
l=i-k;
r=i+k;
}
}
l=0,r=-1;
for(int i=0;i<n;i++)
{
int k=0;
if(i<=r)
k=min(B[l+r-i+1],r-i+1);
while(i-k-1>=0 && i+k<n && S[i-k-1]==S[i+k])
k++;
B[i]=k;
k--;
if(i+k>r)
{
l=i-k-1;
r=i+k;
}
}
}
void Print()
{
for(int i=0;i<n;i++)
ans+=A[i];
for(int i=0;i<n;i++)
ans+=B[i];
fout<<ans<<'\n';
}
int main()
{
Read();
Manacher();
Print();
}