Cod sursa(job #3024917)
Utilizator | Data | 17 martie 2023 11:04:57 | |
---|---|---|---|
Problema | PScPld | Scor | 60 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 0.7 kb |
#include <fstream>
using namespace std;
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
char a[1000010];
char x;
int k;
int rz[1000010];
int main()
{
a[k++]='#';
while(cin>>x)
{
a[k++]=x;
a[k++]='#';
}
int r=0,l=0;
for(int i=0;i<k;i++)
{
if(i>r)
rz[i]=0;
else
rz[i]=min(r-i,rz[l+r-i]);
while(i-rz[i]>=0 && a[i-rz[i]]==a[i+rz[i]])
rz[i]++;
rz[i]--;
if(i+rz[i]>r)
{
r=i+rz[i];
l=i-rz[i];
}
}
long long suma=0;
for(int i=0;i<k;i++)
suma=suma+(rz[i]+1)/2;
cout<<suma;
return 0;
}