Pagini recente » Cod sursa (job #904171) | Cod sursa (job #1492295) | Cod sursa (job #960237) | Cod sursa (job #312449) | Cod sursa (job #2763516)
#include <fstream>
//#define int long long
using namespace std;
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
int afd[2000005];
int 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();
long long lmost=-1,rmost=-1,total=0;
for(i=0; i<n; i++) {
long long r;
if(i>rmost)
r=1;
else {
r=min(rmost-i+1,(long long)afd[lmost+rmost-i]);
r=min(r,(long long)min(i+1,n-i));
}
while(r<=i && i+r<n && s[i+r]==s[i-r])
r++;
afd[i]=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 << '\n';
//for(i=0; i<n; i++)
//cout << s[i] <<' ';
cout << total << '\n';
return 0;
}