Pagini recente » Cod sursa (job #106698) | Cod sursa (job #1634872) | Cod sursa (job #1082029) | Cod sursa (job #1140612) | Cod sursa (job #1179220)
#include<fstream>
#include<string>
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
const int Nmax = 1000001;
string s,S;
int P[2*Nmax],Add[2*Nmax];
int main(){
in>>s;
for(int i=0;i<s.size();i++) S+='#',S+=s[i]; S+="#$";
int C=0,R=0;
for(int i=0;i<S.size();i++){
int j=2*C-i;
if(R > i) P[i]=min(R-i, P[j]);
while (S[i+1+P[i]]==S[i-1-P[i]]) P[i]++;
if (i+P[i] > R) C=i , R=i+P[i];
}
long long Many=s.size();
for(int i=0;i<S.size();i++){
if(S[i]=='#') Add[i]=P[i]-P[i]/2;
else Add[i]=P[i]-P[i]/2-P[i]%2;
}
for(int i=0;i<S.size();i++) Many+=Add[i];
out<<Many<<'\n';
return 0;
}