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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
/* algorytm manachera standardowy */

/* ze strony inernetowej */



#include "palindromy.h"
#include "message.h"

#include <algorithm>
#include <iostream>

#include<vector>
#include<cstring>
#include<string>
#include<map>
#include<set>
#include<algorithm>
#include<stdlib.h>
#include<stdio.h>
using namespace std;

typedef long long LL;
 long long N; 
const int maxn=5000000;
char org[2*maxn];
char str[2*maxn];
int R[maxn*2];
int np[maxn];

/* manacher algorithm,find longest palindromic
 * substring in O(n) time.
 * R[i] is the longest Radius of palindrome include i*/
int calcR()
{
	/* pre-work,make a string "abc"=>"#a#b#c#"
	 * "abcd"=>"#a#b#c#d#",so the even numbers of
	 * palindrome is easily to solve.*/
	int i;
    int size = 0;
	str[0]='@';size++;
	for(i=0;i<N;++i)
	{
        str[size++]='#';
		str[size++]=org[i];
	}
	str[size++]='#';
	
	
	int mx=0,id=0;
	for(i=1;i<size;++i)
	{
		R[i]=mx>i?min(mx-i,R[id*2-i]):1;
		while(i+R[i]<size && i-R[i]>=0 && 
				str[i+R[i]]==str[i-R[i]]) ++R[i];
		if(mx<i+R[i])
		{
			mx=i+R[i];
			id=i;
		}
	}
    return size;
}
int main()
{
    if(MyNodeId() != 0){
       return EXIT_SUCCESS;
    }
   N = GetLength();

  for (int i = 0; i < N; ++i) 
    org[i] =GetLetter(i);
	
	int n = calcR();
	
    long long ile = 0;
    for(int i=0;i<n;++i)  {
        ile+=R[i]/2;
    }
    //  if (MyNodeId() == 0) { 
    cout<<ile<<"\n";
   //   }

	return 0;
}