Pagini recente » Cod sursa (job #168297) | Cod sursa (job #1445246) | Cod sursa (job #1873585) | Cod sursa (job #2378351) | Cod sursa (job #2763503)
#include <fstream>
#define int long long
using namespace std;
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
int afd[2000005];
signed main() {
int i;
int n;
string temp,s;
cin >> temp;
s="";
for(i=0; i<temp.size()-1; i++) {
s+=temp[i];
s+="|"; // nu da TLE pls nu da TLE
}
s+=temp[temp.size()-1];
n=s.size();
int lmost=-1,rmost=-1,total=0;
for(i=0; i<n; i++) {
int& r=afd[i];
if(i>rmost)
r=1;
else {
r=min(rmost-lmost+1,afd[lmost+rmost-i]);
}
while(r<=i && i+r<n && s[i+r]==s[i-r])
r++;
r--;
if(i+r>rmost) {
rmost=i+r;
lmost=i-r;
}
if(s[i]=='|')
total+=(r+1)/2;
else
total+=r/2+1;
}
cout << total << '\n';
return 0;
}