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
#include "message.h"
#include "palindromy.h"
#include<cstdio>
#include<cstring>
#include<cassert>
#include<algorithm>
#include<queue>
#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define FORD(i,a,b) for(int i=(a);i>=(b);--i)
#define foreach(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define all(c) (c).begin(),(c).end()
#define scanf(...) scanf(__VA_ARGS__)?:0
#define e1 first
#define e2 second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int n,sr,p[100000001];
char s[100000001];
ll ans;
int main()
{
	if (MyNodeId()!=0) return 0;
	n=GetLength();
	FOR(i,1,n) s[i]=GetLetter(i-1);
	FOR(i,1,n)
	{
		if (i<=sr+p[sr]-1) p[i]=min(sr+p[sr]-i,p[sr-i+sr]);
		while (i+p[i]<=n && s[i+p[i]]==s[i-p[i]]) p[i]++;
		if (i+p[i]>sr+p[sr]) sr=i;
		ans+=p[i];
	}
	sr=0; memset(p+1,0,sizeof(int)*n);
	FOR(i,1,n)
	{
		if (i<=sr+p[sr]) p[i]=min(sr+p[sr]-i,p[sr-i+sr]);
		while (i+p[i]<n && s[i+p[i]+1]==s[i-p[i]]) p[i]++;
		if (i+p[i]>sr+p[sr]) sr=i;
		ans+=p[i];
	}
	printf("%lld",ans);
}