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
//Lukasz Janeczko Krakow
#include <iostream>
#include <vector>
#include <algorithm>
#include "palindromy.h"
#include "message.h"
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    if(MyNodeId()==0)
        {
            int n=GetLength(); vector <char> c(2*n+1);
            for(int i=0; i<n; i++)
                {
                    c[2*i]=GetLetter(i);
                    c[2*i+1]='#';
                }
            c[2*n]='$';
            vector <int> P(2*n+1,1); int k=0;
            for(int i=1; i<2*n; i++)
                {
                    if(k+P[k]>i)
                        P[i]=max(1,min(P[2*k-i],k+P[k]-i));
                    while(P[i]<=i && c[i+P[i]]==c[i-P[i]])
                        P[i]++;
                    if(i+P[i]>k+P[k])
                        k=i;
                    //cout << i << " " << P[i] <<endl;
                }
            long long ans=1;
            for(int i=1; i<n; i++)
                ans+=(P[2*i]+1)/2;
            for(int i=0; i<n-1; i++)
                ans+=(P[2*i+1])/2;
            cout << ans <<endl;
        }
    return 0;
}