Mai intai trebuie sa te autentifici.
Cod sursa(job #2068930)
Utilizator | Data | 18 noiembrie 2017 11:38:30 | |
---|---|---|---|
Problema | PScPld | Scor | 70 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.82 kb |
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
string txt;
int lp[2000004];
int c=1,r=2;
int sim,dd;
int leg;
long long rez=1;
int main()
{
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
getline(cin,txt);
leg=txt.length();
leg=2*leg+1;
lp[1]=1;
for(int i=2; i<leg; ++i)
{
sim=2*c-i;
dd=r-i;
if(dd>0)
lp[i]=min(lp[sim],dd);
while(i+lp[i]<leg && i-lp[i]>0 && ((i+lp[i]+1)%2==0 || txt[(i+lp[i]+1)/2]==txt[(i-lp[i]-1)/2]))
{
lp[i]++;
}
if(i+lp[i]>r)
{
c=i;
r=lp[i]+i;
}
if(i%2==1)
rez+=(lp[i]+1)/2;
else
rez+=lp[i]/2;
}
cout<<rez;
return 0;
}