P1117

跟这道题很像:CF319D（这也是黑色的）（和我写的这道题的的博客）

分析

这是一道后缀SA+ST的题目，但是众所周知字符串哈希是一种异常优秀的算法，所以我们使用字符串哈希解决这一道问题。在这道题中字符串哈希相比于SA的方法虽然慢了一个$O(logn)$，但是依旧在复杂度可承受范围内。

在这道题中我们需要求出拆分为AABB形态的方案数量。而我们发现AABB形态就是由两个AA状态的字符串连接形成。

如果我们设$A_i$表示以i位结尾的AA串数量，以$B_i$表示以i位开头的AA串数量。则很显然若我们将第i位及以前的部分放一个AA串，在第i+1及以后放一个AA串，他们就可以连在一起成为一个AABB串，所以当前状态对答案的贡献即为$A_i * B_i$。

如果我们可以求解出$A$和$B$，则答案即为：

$$\sum\limits_{i=1}^{n-1}A_i*B_{i+1}$$

现在的问题就是如何求解出A数组与B数组。

如果我们在字符串上每隔$len$设置一个观察点，相邻观察点的最长公共前缀（LCP）与最长公共后缀（LCS）加起来构成的字符串即为经过两点上的最长相同串，并且若$LCP+LCS>=len$，说明它们相交。若相交有重叠部分，则我们可以通过平移得到多个可行的摆放方案，可以缩短两个区间的尾部，也可以缩短两个区间的头部以使他们不重合（详见代码）。

至于如何求LCP和LCS，当然可以用SA，不过我们这里还是采用字符串哈希，毕竟它写起来十分简易。

代码

#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;
const int maxn = 30005;

int a[maxn], b[maxn];
long long w[maxn], p[maxn];
char s[maxn];

inline int get(int l, int r)
{ //计算字符串中l~r段的哈希值
    return ((w[r] - w[l - 1] * p[r - l + 1]) % mod + mod) % mod;
}

int n, now;

int lcp(int x, int y) //求最长前缀
{
    int l = 0, r = now;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (get(x - mid + 1, x) == get(y - mid + 1, y))
            l = mid;
        else
            r = mid - 1;
    }
    return l;
}

int lcs(int x, int y) //求最长后缀
{
    int l = 0, r = n - y + 1;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (get(x, x + mid - 1) == get(y, y + mid - 1))
            l = mid;
        else
            r = mid - 1;
    }
    return l;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        scanf("%s", s + 1);
        n = strlen(s + 1);
        p[0] = 1;
        for (int i = 1; i <= n; i++)
        { //字符串哈希
            p[i] = p[i - 1] * 31 % mod;
            w[i] = (w[i - 1] * 31 + s[i] - 'a') % mod;
        }
        for (int len = 1; len <= n; len++)
        {                              //从小到大枚举删除区间的长度
            int j = len, k = len << 1; //两个观察点
            now = len;
            while (k <= n)
            {
                int LCP = lcp(j, k), LCS = lcs(j, k);
                int hd = max(k - LCP + len, k), tl = min(k + LCS - 1, k + len - 1); //两个块的尾位置
                if (hd <= tl)
                {
                    a[hd]++, a[tl + 1]--;                         //两个尾部之间的空间
                    b[hd - len * 2 + 1]++, b[tl - len * 2 + 2]--; //两个头部之间的空间
                }
                j += len, k += len; //转移到下一个观察点
            }
        }
        for (int i = 1; i <= n; i++)
            a[i] += a[i - 1], b[i] += b[i - 1];
        long long answer = 0;
        for (int i = 1; i < n; i++)
            answer += a[i] * b[i + 1];
        printf("%lld\n", answer);
    }
    return 0;
}