BZOJ 4650
题意：如果一个字符串可以被拆分为 $AABB$ 的形式，其中 $A$ 和 $B$ 是任意非空字符串，则我们称该字符串的这种拆分是优秀的。给出一个长度为 $n$ 的字符串 $S$，我们需要求出，在它所有子串的所有拆分方式中，优秀拆分的总个数。
本题直接无脑Hash有85分，思考一下，可以发现$AA$和$BB$本质上相同，只需要统计每个位置向左向右可能有几种$AA$串，乘法原理即可。这个Hash有95分。(发现这个方法我还是用后缀数组想的时候推出来的，但是没想出后缀数组做法没有回来用Hash暴力…)
后缀数组做的话也要用到上面的方法，考虑枚举$AA$串的$len$，然后在字符串上每$len$个字符作一个「关键点」，可以发现每个当前$AA$串必过两个「关键点」。
考虑两个「关键点」。假设$LCP$是这两个「关键点」的最长公共前缀，$LCS$是这两个「关键点」的最长公共后缀(不是最长公共子序列)，那么
当$LCS+LCP \leq len$时
当$LCS+LCP \geq len$时
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
int T;
namespace flyinthesky {
const int MAXN = 30000 + 5, LOGS = 17;
struct suffixArray {
char a[MAXN];
int n, m, SA[MAXN], rk[MAXN], height[MAXN], tp[MAXN], tax[MAXN];
int f[MAXN][LOGS + 5], lg2[MAXN];
void build() {
ms(SA, 0), ms(rk, 0), ms(height, 0), ms(tp, 0);
for (int i = 0; i <= m; ++i) tax[i] = 0;
for (int i = 1; i <= n; ++i) tax[rk[i] = a[i]]++;
for (int i = 1; i <= m; ++i) tax[i] += tax[i - 1];
for (int i = n; i >= 1; --i) SA[tax[rk[i]]--] = i;
for (int k = 1; k <= n; k <<= 1) {
int p = 0;
for (int i = n - k + 1; i <= n; ++i) tp[++p] = i;
for (int i = 1; i <= n; ++i) if (SA[i] > k) tp[++p] = SA[i] - k;
for (int i = 0; i <= m; ++i) tax[i] = 0;
for (int i = 1; i <= n; ++i) tax[rk[tp[i]]]++;
for (int i = 1; i <= m; ++i) tax[i] += tax[i - 1];
for (int i = n; i >= 1; --i) SA[tax[rk[tp[i]]]--] = tp[i];
swap(rk, tp), p = rk[SA[1]] = 1;
for (int i = 2; i <= n; ++i) {
rk[SA[i]] = (tp[SA[i]] == tp[SA[i - 1]] && tp[SA[i] + k] == tp[SA[i - 1] + k]) ? p : ++p;
}
if (p >= n) break ;
m = p;
}
int k = 0;
for (int i = 1; i <= n; ++i) {
if (k) --k;
int j = SA[rk[i] - 1];
while (a[i + k] == a[j + k]) ++k;
height[rk[i]] = k;
}
}
void buildst() {
ms(f, 0);
lg2[0] = -1; for (int i = 1; i <= n; ++i) lg2[i] = lg2[i >> 1] + 1; lg2[0] = 0;
for (int i = 1; i <= n; ++i) f[i][0] = height[i];
for (int j = 1; (1 << j) <= n; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
int LCP(int l, int r) {
l = rk[l], r = rk[r];
if(l > r) swap(l, r); l++;
int k = lg2[r - l + 1];
return min(f[l][k], f[r - (1 << k) + 1][k]);
}
}sa[2];
int cfa[MAXN], cfb[MAXN];
void clean() {
ms(cfa, 0), ms(cfb, 0);
}
int solve() {
clean();
scanf("%s", sa[0].a + 1);
sa[0].n = strlen(sa[0].a + 1), sa[0].m = 256;
for (int i = 1; i <= sa[0].n; ++i) sa[1].a[i] = sa[0].a[sa[0].n - i + 1];
sa[1].n = sa[0].n, sa[1].m = 256;
sa[0].build(), sa[1].build();
sa[0].buildst(), sa[1].buildst();
for (int len = 1; len <= sa[0].n / 2; ++len) {
for (int i = len; i + len <= sa[0].n; i += len) {
int l = i, r = i + len;
int L = sa[0].n - (r - 1) + 1, R = sa[0].n - (l - 1) + 1;
int lcp = sa[0].LCP(l, r); lcp = min(lcp, len);
int lcs = sa[1].LCP(L, R); lcs = min(lcs, len - 1);
if (lcp + lcs >= len) {
int g = lcp + lcs - len;
cfa[l - lcs]++, cfa[l - (lcs - g) + 1]--;
cfb[r + (lcp - g) - 1]++, cfb[r + lcp]--;
}
}
}
for (int i = 1; i <= sa[0].n; ++i) cfa[i] += cfa[i - 1], cfb[i] += cfb[i - 1];
LL ans = 0;
for (int i = 1; i <= sa[0].n; ++i) ans += 1.0 * cfa[i] * cfb[i - 1];
printf("%lld\n", ans);
return 0;
}
}
int main() {
scanf("%d", &T);
while (T--) flyinthesky::solve();
return 0;
}
