Pagini recente » Cod sursa (job #1325215) | Cod sursa (job #2169400) | Cod sursa (job #2366357) | Cod sursa (job #198190) | Cod sursa (job #2798375)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
const int N = 2000005;
int v[N];
int main()
{
int n, radius = 0, center = 0;
long long result = 0;
string s1, s2 = "";
in >> s1;
s2 += "(*";
//n = s1.size();
for(char c:s1){
s2 += c;
s2 += "*";
}
s2 += ")";
n = s2.size();
for(int i = 1; i < n; i++){
int opposite = - i + center * 2;
if(i < center + radius){
v[i] = min(center + radius - i, v[opposite]);
}
while(s2[i + v[i] + 1] == s2[i - v[i] - 1]){
v[i]++;
}
if(i + v[i] > center + radius){
center = i;
}
radius = v[i];
}
for(int i = 1; i < n; i++){
result += (v[i] + 1) / 2;
}
out << result;
return 0;
}