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 <bits/stdc++.h>
#include "message.h"
#include "palindromy.h"

using namespace std;

int id, n;

long long manacher() {
    long long ret = 0;
    vector<int> R;
    int i = 0;
    int t = 0;
    while (i < n)
    {
        while (i - t >= 0 && i + t + 1 < n && GetLetter(i - t) == GetLetter(i + t + 1)) t++;
        R.push_back(t);
        ret += R.back();

        int k = 1;
        while (k <= t && R[i - k] != R[i] - k)
        {
            R.push_back(min(R[i - k], R[i] - k));
            ret += R.back();
            k++;
        }
        t = max(0, t - k);
        i += k;
    }
    R.clear();

    i = 0;
    t = 0;
    while (i < n)
    {
        while (i - t >= 0 && i + t < n && GetLetter(i - t) == GetLetter(i + t)) t++;
        R.push_back(t);
        ret += R.back();

        int k = 1;
        while (k < t && R[i - k] != R[i] - k)
        {
            R.push_back(min(R[i - k], R[i] - k));
            ret += R.back();
            k++;
        }
        t = max(0, t - k);
        i += k;
    }
    return ret;
}
int main() {

    id = MyNodeId();
    if (id != 0) return 0;
    n = GetLength();

    long long ans = manacher();

    printf("%lld\n", ans);

    return 0;
}