题解：P9873 [EC Final 2021] Beautiful String

· · 题解

题意：定义 a+b 表示将字符串 b 接在字符串 a 后。

有 T 组询问，每次给定一个字符串 S，找出其所有子串 s 满足其可以表示为 s=s_1+s_2+s_3+s_4+s_5+s_6 的形式，其中 s_1=s_2=s_5,s_3=s_6。

数据范围： |S| \le 5 \times 10^3，\sum|S| \le 3\times 10^4。

solution

我不会告诉你部分分怎么写的，我也不会告诉你我eps暴力怎么炸的。

令 n 表示字符串 S 的长度，则我们希望我们能得到一个单次 O(n^2) 的做法。

题目给定子串模式为 AABCAB，你肯定要找一个枚举点作为突破。而这题的突破点就在于：里面出现了两次 AB。你枚举前一个 AB，为了满足要求，这个 AB 前面的部分要求是这个 AB 的一个前缀，后面只需要隔了至少一个不等于 A 且不等于 B 的间隔，然后再有一个完全一样的东西拼起来即可。

所以做法已经呼之欲出了：枚举 AB 作为整体，如果能检查其前面有多少个其前缀，后面有多少个完全一样的 AB ，那么把这两个值乘法原理乘起来，就是当前枚举的 AB 产生的贡献。

形式化地讲：令 t=s_2+s_3，在固定了 t 的位置后，就只需要知道 t 的前面有多少个子串和 t 的前缀相同，在 t 的后面还有多少个和 t 完全相同的子串，这两个值乘起来就是 t 产生的贡献。

设 f_{i,j} 表示 t=S[i,...,i+j-1] 时，在第 i+j 个位置后面还有多少个与 t 相同的子串。设 g_{i,j} 表示 t=S[i,...,i+j-1] 时，在 t 之前有多少个子串是 t 的前缀，那么答案就是 \sum f_{i,j}\times g_{i,j}。

至于如何求出 f,g：枚举两个位置 i,j，并求出 S[i,...,n] 和 S[j,...,n] 的最长公共前缀 lcp，然后令 f_{i,lcp}=f_{i,lcp}+1，最后再给 f 数组的第二维求一个后缀和，即可得到定义中的 f 数组。g 数组则更为方便，只需要判断 S[i,...,n] 和 S[i-j,...,n] 的最长公共前缀是否大于等于 j 即可。

那如何 O(1) 地求出最长公共前缀呢？递推即可。倒序枚举，如果 S_i=S_j，则 lcp_{i,j}=lcp_{i+1,j+1}+1，否则 lcp_{i,j}=0。 当然，你也可以后缀数组搞一下。

最后统计时注意 s_i(i\in{1,2,3,4,5,6}) 都不能为空。做完了。

Main Code：

void mian() {
    cin >> S;
    n = S.length(); S = ' ' + S;
    for(int i = n; i; i--)
        for(int j = i; j <= n; j++)
            if(S[i] == S[j])
                lcp[i][j] = lcp[i + 1][j + 1] + 1;
    for(int i = 2; i <= n; i++)
        for(int j = i + 3; j < n; j++) {
            int k = min(j - i - 1, lcp[i][j]);
            if(k >= 2) f[i][k]++;
        }
    for(int i = 2; i <= n; i++)
        for(int j = n - 1; j > 1; j--) f[i][j] += f[i][j + 1];
    for(int i = 2; i <= n; i++)
        for(int j = 1; j <= min(i - 1, n - i + 1); j++) 
            if(lcp[i - j][i] >= j) g[i][j]++;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++) g[i][j] += g[i][j - 1];
    long long ans = 0;
    for(int i = 2; i <= n; i++)
        for(int j = 2; j <= n; j++) ans += 1ll * f[i][j] * g[i][j - 1];
    cout << ans << '\n';
    memset(f, 0, sizeof(f));
    memset(g, 0, sizeof(g));
    memset(lcp, 0, sizeof(lcp));
}

当然，其实我还口胡了一个哈希。

对于找在子串 t 后还有多少与 t 完全相同的子串，如果将后面的所有串都放入哈希表，那么肯定是跑不动的。所以我们将后面所有串按长度分类放入哈希表。因为当你子串 t 的长度知道后，哈希表中的那个串长度也定了，也就可以快速地找后面的完全相同的 t 了。

而对于在子串 t 前寻找一个前缀，只需要枚举前缀前的一个端点，将这个端点到 t 左端点的串和 t 用哈希判一下，再用一个类似后缀和的东西拼上去。

说不太清楚，应该是对的。