Pagini recente » Cod sursa (job #2021613) | Cod sursa (job #890052) | Cod sursa (job #851175) | Cod sursa (job #1902679) | Cod sursa (job #2866192)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
string s;
int n;
void Manacher()
{
if (n == 0){
fout << 0 << '\n';
return;
}
int N = 2 * n + 1;
int L[N];
L[0] = 0;
L[1] = 1;
// C = centerPosition, R = centerRightPosition, i = currentRightPosition
// iMirror = currentLeftPosition
int C = 1, R = 2, iMirror, diff = -1;
for (int i=2;i<N;i++){
iMirror = 2 * C - i;
L[i] = 0;
diff = R - i;
if (diff > 0){
L[i] = min(L[iMirror], diff);
}
while((i+L[i]) < N && (i-L[i])>0 && ( ((i+L[i]+1)%2 == 0)
|| (s[(i+L[i]+1)/2] == s[(i-L[i]-1)/2])) ){
L[i] ++;
}
if (i + L[i] > R){
C = i;
R = i + L[i];
}
}
long long ans = 0;
for (int i=0;i<N;i++){
ans += (L[i] + 1) / 2;
}
fout << ans << '\n';
}
int main() {
getline(fin, s);
n = s.size();
Manacher();
return 0;
}