Pagini recente » Cod sursa (job #63942) | Cod sursa (job #2232081) | Cod sursa (job #628694) | Cod sursa (job #2931541) | Cod sursa (job #1104304)
#include<fstream>
#define N 1000100
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
int c,poz,rez,l,dr,i,lg,sol[N*2];
char s[2*N],s1[N];
inline int cauta(int st,int dr)
{
int sol=0;
while(st>=0&&dr<=lg&&s[st]==s[dr])
--st,++dr,++sol;
return sol;
}
int main()
{
f>>s1;
lg=-1;
for(i=0;s1[i];++i)
{
s[++lg]=s1[i];
s[++lg]='*';
}
c=-1;
dr=-1;
for(i=0;i<=lg;++i)
{
if(i>dr)
{
sol[i]=cauta(i-1,i+1);
if(sol[i])
{
dr=i+sol[i];
c=i;
}
}
else
{
poz=2*c-i;
l=dr-i;
if(sol[poz]<l)
{
sol[i]=sol[poz];
continue;
}
sol[i]=l+cauta(i-l-1,i+l+1);
if(sol[i]+i>dr)
{
dr=sol[i]+i;
c=i;
}
}
}
rez=0;
for(i=0;i<=lg;++i)
if(s[i]=='*')
rez+=1LL*((sol[i]+1)/2);
else
rez+=1LL*(sol[i]/2+1);
g<<rez<<'\n';
return 0;
}