1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <algorithm>
#include <stdio.h>
#include "palindromy.h"
#include "message.h"
#define ll long long

using namespace std;

int n=(int)GetLength();
int l, r;
long long w;
const int id=MyNodeId();
const int nn=NumberOfNodes();

char s(int x){
    return GetLetter((ll)x);
}

int main() {
    if(id>0)return 0;
    int *t;
    t=new int[n];
	l=-1;
	r=-1;
	for (int i = 0; i < n; i++)t[i]=0;
	for (int i = 0; i < n; i++) {
		int in = 1;
		if (i < r)
			in = min(r - i + 1, t[l + r - i]);
		while (i + in < n && i - in >= 0 && s(i - in) == s(i + in))
			in++;
		t[i] = in;
		if (i + in - 1 > r) {
			l = i - in + 1;
			r = i + in - 1;
		}
	}
	for (int i = 0; i < n; i++) {
		if (t[i] > 1) {
			w=w+((ll) t[i] - 1);
		}
		t[i]=0;
	}
	l=-1;
	r=-1;
	for (int i = 0; i < n; i++) {
		int in = 0;
		if (i < r)
			in = min(r - i + 1, t[l + r - i + 1]);
		while (i + in < n && i - 1 - in >= 0 && s(i - 1 - in) == s(i + in))
			in++;
		t[i] = in;
		if (i + in - 1 > r) {
			l = i - in;
			r = i + in - 1;
		}
	}
	for (int i = 0; i < n; i++) {
		if (t[i])w=w+((ll)t[i]);
	}
    printf("%lld",w);
	return 0;
}