Cod sursa(job #2442520)
Utilizator | Bogdan Gavra gavra_bogdan | Data | 24 iulie 2019 11:43:58 |
---|---|---|---|
Problema | PScPld | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 1.17 kb |
#include <bits/stdc++.h>
using namespace std;
char c[2000005];
int mx[2000005];
int main()
{
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
int n,dr=0,st=0;
string s;
cin>>s;
n=s.size();
for(int i=0;i<n;i++)
{
c[2*i+1]=s[i];
c[2*(i+1)]='*';
}
c[0]='*';
n*=2;
for(int i=1;i<=2*n;i++)
{
if(i<=dr)
{
int o=st+dr-i;
mx[i]=mx[o];
int jdr=i+mx[i],jst=i-mx[i];
while(jst>=0 and jdr<=n and c[jdr]==c[jst])
{
jdr++;
jst--;
mx[i]++;
}
if(dr<i+mx[i]-1)
{
dr=i+mx[i]-1;
st=i-mx[i]+1;
}
}
else
{
int jdr=i,jst=i;
while(jst>=0 and jdr<=n and c[jdr]==c[jst])
{
jdr++;
jst--;
mx[i]++;
}
dr=i+mx[i]-1;
st=i-mx[i]+1;
}
}
int sum=0;
for(int i=1;i<=n;i++)
sum+=mx[i]/2;
cout<<sum;
return 0;
}