波特题。strong。

首先发现 A,B 之间互不影响，考虑枚举分割线 $i$，定义 $f(i)$ 表示以 $i$ 为结尾的 AA 串个数，$g(i)$ 表示以 $i$ 为开头的 AA 串个数。则答案为 $\sum\limits_{i=1}^{n-1} f(i)g(i+1)$。

然后发现直接 hash $\mathcal O(n^2)$ 求 $f(i),g(i)$ 就能拿 95pts，考场上就不用考虑正解了，直接冲 hash。但是练习还是要学一下的。

观察 AA 串中，两个 A 串的开头距离为 $|A|$。

考虑枚举 $w=|A|$，用一个波特才能想到的技巧：每隔 $w$ 撒一个点。这样每个 AA 串恰经过相邻两点。

设相邻两点分别为 $x,y$，定义 $\mathrm{lcp}(x,y)$ 表示以 $x,y$ 为开头的后缀的最长公共前缀，$\mathrm{lcs}(x,y)$ 表示以 $x,y$ 为结尾的前缀的最长公共后缀。

画个图就会发现，若有 AA 串经过 $x,y$，则必有 $\mathrm{lcp}(x,y)+\mathrm{lcs}(x,y)\ge w$，且这是 AA 串存在的充要条件。

然后又发现，$\mathrm{lcp}(x,y)+\mathrm{lcs}(x,y)$ 可能比 $w$ 大，此时有连续的一段点是 AA 串的开头/结尾，用两个差分数组维护即可。

时间复杂度：$\mathcal O(n(\log n+\ln n))$。