Pagini recente » Cod sursa (job #1914073) | Cod sursa (job #141210) | Cod sursa (job #1558373) | Cod sursa (job #748377) | Cod sursa (job #2763501)
#include <fstream>
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();
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;
}