Pagini recente » Cod sursa (job #497349) | Cod sursa (job #158017) | Cod sursa (job #450212) | Cod sursa (job #885811) | Cod sursa (job #1969860)
/**
* Worg
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
FILE *fin = freopen("pscpld.in", "r", stdin);
FILE *fout = freopen("pscpld.out", "w", stdout);
const int kMaxN = 1 + 1000000;
/*-------- Data --------*/
int N;
char initial[kMaxN], transformed[kMaxN * 2 + 5];
int len[kMaxN * 2 + 5];
/*-------- --------*/
void GetTransformed() {
for(int i = 1; i <= N; i++) {
transformed[i << 1] = initial[i];
}
N = (N << 1) + 1;
for(int i = 1; i <= N; i += 2) { // Pe pozitii impare punem caractere speciale
transformed[i] = '$';
}
}
long long ManacherAlgorithm(char *s, const int N) {
long long answer = 0;
int index = 0, center = 0;
for(int i = 1; i <= N; i++) {
if(i <= index) {
len[i] = std::min(index - i + 1, len[center - (i - center)]);
}
while(i - len[i] >= 1 && i + len[i] <= N && s[i + len[i]] == s[i - len[i]]) {
len[i] ++;
}
answer += len[i] / 2;
if(i + len[i] - 1 > index) {
index = i + len[i] - 1;
center = i;
}
}
return answer;
}
int main() {
scanf("%s", initial + 1); N = std::strlen(initial + 1);
GetTransformed();
printf("%lld\n", ManacherAlgorithm(transformed, N));
return 0;
}