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
86
87
88
89
90
91
92
93
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
inline bool isprime(ll num)
{if(num==2||num==3)return true;
if(num%6!=1&&num%6!=5)return false;
for(int i=5;1ll*i*i<=num;i+=6){if(num%i==0||num%(i+2)==0)return false;}
return true;}
const int mod = 1e9+7;
inline ll mul(ll a,ll b,ll c){return (a*b-(ll)((ld)a*b/c)*c+c)%c;}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll g = exgcd(b,a%b,y,x);y-=a/b*x;return g;}
inline ll quick_pow(ll a,ll b,ll mod){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll quick_pow(ll a,ll b){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll inv(ll x){return quick_pow(x,mod-2);}
inline ll inv(ll x,ll mod){return quick_pow(x,mod-2,mod);}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
const int N = 5e5+10;
char s[N];
int a[N];
char ma[N<<1];
int tree[N];
int n;
int mc[N<<1];
int lowbit(int x){
return x&(-x);
}
void add(int x,int k){
while(x<=n){
tree[x]+=k;
x+=lowbit(x);
}
}
int query(int x){
int ans = 0;
while(x>0){
ans+=tree[x];
x-=lowbit(x);
}
return ans;
}
void manacher(char s[],int len){
int l = 0;
ma[l++]='$';ma[l++]='#';
for(int i=0;i<len;i++){
ma[l++]=s[i];
ma[l++]='#';
}
int mx = 0, id = 0;
for(int i=0;i<l;i++){
mc[i]=mx>i?min(mc[2*id-i],mx-i):1;
while(ma[i+mc[i]] == ma[i-mc[i]])mc[i]++;
if(i+mc[i]>mx){
mx = i+mc[i];
id = i;
}
}
}
int cmp(pair<int,int>a, pair<int,int>b){
if(a.first!=b.first)return a.first>=b.first;
else return a.second>b.second;
}
vector<pair<int,int>>v;
void solve(){
scanf("%s",s);
n = strlen(s);
for(int i=1;i<=2*n+10;i++)mc[i]=0;
for(int i=1;i<=n;i++)tree[i]=0;
manacher(s,n);
v.clear();
for(int i=1;i<=n;i++){
a[i]=mc[i*2]/2-1;
v.push_back({mc[i*2]/2-1,i});
}
sort(v.begin(),v.end(),cmp);
ll ans = 0;
for(int i=0;i<v.size();i++){
int pos = v[i].second;
int len = v[i].first;
int l = pos-len;
int r = pos+len;
ans+=query(r) - query(l-1);
add(pos,1);
}
printf("%lld\n",ans);
}
int main(){
int t;
scanf("%d",&t);
while(t--)solve();
}
|
