Cod sursa(job #2545842)
Utilizator | Data | 13 februarie 2020 16:31:48 | |
---|---|---|---|
Problema | PScPld | Scor | 30 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 0.63 kb |
#include <fstream>
using namespace std;
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
string sir,a;
int c,dr,ex[1000100], ans, lg;
int main()
{
cin>>sir;
a+='#';
for(int i=0; i<sir.size(); ++i)
{
a+=sir[i];
a+='#';
}
ex[0]=1;
c=0; dr=0;
for(int i=1; i<a.size(); ++i)
{
lg=1;
if(i<=dr)
lg=min(ex[2*c-i],dr-i+1);
while(i>=lg && i+lg<a.size() && a[i-lg]==a[i+lg])
++lg;
if(i+lg-1>dr)
dr=i+lg-1, c=i;
ex[i]=lg;
ans+=ex[i]/2;
}
cout<<ans<<'\n';
return 0;
}