Pagini recente » Cod sursa (job #2728142) | Cod sursa (job #2188706) | Cod sursa (job #305002) | Cod sursa (job #782619) | Cod sursa (job #2798424)
#include <bits/stdc++.h>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
const int N = 2e6 + 5;
int v[N];
string s1, s2;
int main()
{
long long result = 0;
in >> s1;
s2 = "(*";
for(char c:s1){
s2 += c;
s2 += "*";
}
s2 += ")";
int n = s2.size(), radius = 0, center = 0;
for(int i = 1; i < n; i++){
int opposite = 2 * center - i, p = center + radius;
if(i < p) v[i] = min(p - i, v[opposite]);
while(s2[i + v[i] + 1] == s2[i - v[i] - 1]) v[i]++;
if(i + v[i] > p)
center = i;
radius = v[i];
}
for(int i = 1; i < n; i++){
result += (v[i] + 1) >> 1;
}
out << result;
return 0;
}