Pagini recente » Cod sursa (job #3251253) | Cod sursa (job #2170228) | Cod sursa (job #582238) | Cod sursa (job #2561255) | Cod sursa (job #2736396)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
string s, t;
using ll = long long;
const int NMAX = 2e6;
int v[NMAX + 5];
int main()
{
ll res = 0;
fin >> s;
t = "(*";
for(char ch : s)
t += ch,
t += "*";
t += ")";
int n = t.length(), radius, center;
for(int i = 1; i < n; i++) {
int mirror = 2 * center - i;
if(i < center + radius) v[i] = min(radius + center - i, v[mirror]);
while(t[i + v[i] + 1] == t[i - v[i] - 1]) v[i]++;
if(i + v[i] > center + radius)
center = i,
radius = v[i];
}
for(int i = 1; i < n; i++)
res += (v[i] + 1) / 2;
fout << res;
return 0;
}