Pagini recente » Cod sursa (job #704893) | Cod sursa (job #1013846) | Statistici Cecilia Ross (pestcontrol883) | Cod sursa (job #471849) | Cod sursa (job #1013073)
#include <fstream>
#include <string.h>
#define Nmax 1000099
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
int N,P[2*Nmax],C,R;
char S[Nmax],T[2*Nmax];
unsigned long long sol;
inline void ReadInput()
{
f.getline(S+1,Nmax,'\n');
N=strlen(S+1);
}
inline void Preprocess()
{
//din "abba" fac "^#a#b#b#a#$"
T[0]='^';T[1]='#';
for(int i=1;i<=N;++i)T[2*i]=S[i],T[2*i+1]='#';
T[2*N+2]='$';
N*=2;
}
inline int FindLPS(char T[])
{
for(int i=1;i<=N;++i)
{
int i_mirror=2*C-i;
if(R>i)P[i]=min(R-i,P[i_mirror]);
else P[i]=0;
while(T[i+1+P[i]] == T[i-1-P[i]])++P[i];
if(i+P[i]>R)
{
C=i;
R=i+P[i];
}
}
}
inline void PrintLPS()
{
int maxLen=0,centerIndex=0;
for(int i=1;i<=N;++i)
if(P[i])sol+=P[i];
g<<sol<<'\n';
//int st=(centerIndex-1-maxLen)/2; g<<st<<'\n';
//for(int i=1;i<=maxLen;++i)g<<S[st+i];
}
int main()
{
ReadInput();
Preprocess();
FindLPS(T);
PrintLPS();
f.close();g.close();
return 0;
}