```
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;
int t;
int fail[1050000];
int cnt[200],sum[1050000],size[1050000][27];
bool b[1050000];
long long ans=0;
void kmp(string s);
void add(int len,int cj);
bool check(int x,int len);
int main(){
freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
cin>>t;
string s;
int len;
int change=0,temp=0;
for(int i=1;i<=t;i++){
cin>>s;
len=s.length();
s='0'+s;
if(len<3){
cout<<"0"<<endl;
continue ;
}
memset(fail,0,sizeof(fail));
memset(b,0,sizeof(b));
memset(cnt,0,sizeof(cnt));
memset(size,0,sizeof(size));
ans=0;
kmp(s);
for(int j=1;j<=len;j++){
temp=s[j]-'a'+1;
cnt[temp]++;
change=(cnt[temp]%2)?1:-1;
sum[j]=sum[j-1]+change;
for(int k=0;k<=26;k++)
size[j][k]=size[j-1][k];
size[j][sum[j]]++;
}
memset(cnt,0,sizeof(cnt));
for(int j=len;j>0;j--){
temp=s[j]-'a'+1;
cnt[temp]++;
change=((cnt[temp])%2)?1:-1;
sum[j]=sum[j+1]+change;
}
for(int j=len-1;j>=2;j--)
add(j,sum[j+1]);
cout<<ans<<endl;
}
return 0;
}
void kmp(string s){
int len=s.length();
int j=0;
for(int i=2;i<len;i++){
while(j>0&&s[j+1]!=s[i])
j=fail[j];
if(s[i]==s[j+1])
j++;
fail[i]=j;
}
}
void add(int len,int cj){
int lenz=len-fail[len];
if(len%lenz){
for(int i=0;i<=cj;i++)
ans+=size[len-1][i];
return ;
}
for(int i=lenz;i<=len;i+=lenz)
if((len%i)==0)
for(int j=0;j<=cj;j++)
ans+=size[i-1][j];
}
```
by abs_0 @ 2020-12-06 11:19:24
我也写的 kmp 啊，许多人都写得 kmp
卡的不好 84（比如我），卡的好 100 呢
by syksykCCC @ 2020-12-06 11:24:05
~~真就我一个手一滑写了个sort然后就100->84吗~~
by Thinking @ 2020-12-06 11:25:39