Pagini recente » Cod sursa (job #348679) | Cod sursa (job #454334) | Cod sursa (job #2867008) | Cod sursa (job #2149220) | Cod sursa (job #2461064)
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#define NMAX 1000000
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
long long v[2*NMAX+100], sol;
string s1;
vector <char> s;
int main()
{
f >> s1;
int n1 = s1.size();
s.push_back('@');
for(int i=0; i<n1; i++)
{ s.push_back('#');
s.push_back(s1[i]);
}
s.push_back('#');
s.push_back('%');
int n = s.size();
long long C=0, R=0;
for(int i=1; i<n-1; i++)
{ long long ogl = 2*C - i;
if(i < R) v[i] = min(R-i, v[ogl]);
while(s[i+v[i]+1] == s[i-v[i]-1]) v[i]++;
if(v[i] + i > R)
{ C = i;
R = v[i] + i;
}
}
for(int i=0; i<n; i++) sol = sol + v[i]/2;
g << sol + n1 << '\n';
return 0;
}