令 $N=| S|$。

首先发现，枚举 $C$ 再判断前缀消耗的时间很多，这样行不通。

转向考虑枚举 $AB$，得出所有的 $(AB)^i$，不难发现可以用哈希+调和做到 $O(N\ln N)$。

现在考虑 $f(A)\le f(C)$ 的限制。

设 $pre(i)=f(S_{1\sim i}),suf(i)=f(S_{i+1\sim n})$。

当前枚举到 $AB$ 的长度为 $x$，则 $AB$ 对答案的贡献为 $\sum\limits_{i}\sum\limits_{j=1}^x [pre(j)\le suf(x\times i+1)]$。

预处理出 $pre(1\sim n),suf(1\sim n)$，用树状数组维护，时间复杂度为 $O(TN\ln N\log N)$。

虽然常数小，但只有 $84\text{pts}$。

仔细地思考下，这个东西真的必须要用树状数组维护吗？

设 $sum(i,j)= \sum\limits_{k=1}^i [pre(i)\le j]$，则 $AB$ 的贡献变为 $\sum\limits_{i}sum(x,x\times i+1)$。

而 $sum$ 数组显然可以用前缀和维护。

时间复杂度 $O(T(N\ln N+N\times 26))$，足以通过。