好多题解用的扩展KMP（没学过，所以不用这种方法）。

我们按照题目要求记F(s)表示s串的权值，可以预处理出前缀权值（用于A）和后缀权值（用于C），枚举AB的长度i=2~n-1，不需要分开枚举，我们只关心A，A可以从1扩展到i-1。有一个性质，不管AB重复多少次，C的权值只有两种，AB重复奇数次有一种，偶数次有一种，不影响C的字符出现次数的奇偶性。所以代码中hc[0]和hc[1]就是用来存这两种结果。要满足F(A)<=F(C)，相当于是前缀查询，可以套一个树状数组（权值作为下标，不超过26）。然后就是枚举重复次数（字符串hash判定），累加答案就行了。

字符串hash的进制数我这里取的是13331，开ull储存，不用处理溢出问题，溢出相当于自动对264 取模。

1 #include
2 using namespace std;
3 #define N 1100000
4 #define ull unsigned long long
5 #define ll long long
6 #define seed 13331
7 char s[N];
8 int pre[N],suf[N],n,cnt[N],nw,t[30],hc[3];
9 ull hx[N],pw[N];
10 void add(int p){
11 ++p;//树状数组不能处理为0的下标，均向右平移一位
12 while(p<=27){ 13 ++t[p]; 14 p+=p&(-p); 15 } 16 } 17 18 ll query(int p){ 19 ll ans=0;++p; 20 while(p){ 21 ans+=t[p]; 22 p-=p&(-p); 23 } 24 return ans; 25 } 26 27 ull gethx(int l,int r){ 28 return hx[r]-hx[l-1]*pw[r-l+1]; 29 } 30 31 int main(){ 32 int _;ll ans; 33 scanf("%d",&_); 34 while(_--){ 35 memset(cnt,0,sizeof(cnt)); 36 memset(t,0,sizeof(t)); 37 scanf("%s",s+1); 38 n=strlen(s+1); 39 nw=0;ans=0; 40 pw[0]=1; 41 for(int i=1;i<=n;i++){ 42 pw[i]=pw[i-1]*seed; 43 hx[i]=hx[i-1]*seed+s[i];//字符串hash 44 cnt[s[i]-'a']^=1;//前缀桶 45 if(cnt[s[i]-'a']) ++nw; 46 else --nw; 47 pre[i]=nw;//前缀权值 48 } 49 memset(cnt,0,sizeof(cnt)); 50 nw=0; 51 for(int i=n;i>=1;i--){//同理，处理后缀权值
52 cnt[s[i]-'a']^=1;
53 if(cnt[s[i]-'a']) ++nw;
54 else --nw;
55 suf[i]=nw;
56 }
57 for(int way,p,i=2;i<n;i++){//i相当于枚举的是AB
58 add(pre[i-1]);//A可以从1扩展到i-1（B不为空）
59 hc[0]=query(suf[i+1]);//AB出现奇数次，C确定，A的可能情况有多少种
60 if(i+i+1<=n) hc[1]=query(suf[i+i+1]);//AB出现偶数次
61 p=i+1;way=0;
62 while(p<=n&&hx[i]==gethx(p-i,p-1)){//枚举重复次数
63 ans+=hc[way];
64 p+=i;
65 way^=1;
66 }
67 }
68 printf("%lld\n",ans);
69 }
70 return 0;
71 }