题目大意:
给定字符串 \(S\),求有多少对不相交的回文串。
对于 \(100\%\) 的数据,\(1 \leq |S| \leq 10 ^ 5\)。
正文:
设 \(pre_i,suf_i\) 分别表示以 \(i\) 为开头的回文串的个数和以 \(i\) 为结尾的回文串的个数,那么答案就是:
\[\sum_{i=1}^{\text{len}}pre_i\sum_{j=1}^{i-1}suf_j
\]
但这个时间复杂度是 \(\mathcal{O}(n^2)\) 的,不能接受。所以设 \(sum_i=\sum_{j=1}^{i}suf_j\)。通过前缀和就可以达到 \(\mathcal{O}(n)\) 的时间复杂度了。
接下来就是求这几个数组了。考虑用 Manacher 算法先计算出以 \(i\) 为中心的回文串半径 \(a_i\),那么 \(\frac{a_i}{2}\) 就是以 \(i\) 为中心的回文个数。可以得到 \(\frac{a_i}{2}\) 可以为 \(pre_j,suf_k\quad(j\in[i,\text{len}],k\in[1,i])\) 贡献。这里可以用差分优化。
代码:
int n;
char s[N], c[N];
ll suf[N], pre[N], sum[N], a[N], ans;
int main()
{
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
while (scanf ("%s", c + 1) != EOF)
{
int len = strlen(c + 1);
n = 0;
s[0] = '$';
s[++n] = '#';
for (int i = 1; i <= len; i++) s[++n] = c[i], s[++n] = '#';
s[n + 1] = '@';
ll p = 1, mx = 1;
for (int i = 1; i <= n; i++)
{
a[i] = min (mx - i, a[2 * p - i]);
while (s[i - a[i]] == s[i + a[i]]) ++a[i];
if (i + a[i] > mx)
mx = i + a[i], p = i;
}
// Manacher
memset (suf, 0, sizeof suf);
memset (pre, 0, sizeof pre);
memset (sum, 0, sizeof sum);
for (int i = 1; i <= 2 * n; i ++)
{
int x = (i + 1) / 2;
suf[x]++, suf[x + a[i] / 2] --;
}
for (int i = 2 * n; i; --i)
{
int x = i / 2;
pre[x]++, pre[x - a[i] / 2] --;
}
for (int i = n; i; --i) pre[i] += pre[i + 1];
for (int i = 1; i <= n; ++i) suf[i] += suf[i - 1], sum[i] = sum[i - 1] + suf[i];
ans = 0;
for (int i = 1; i <= n; i++)
ans += pre[i] * sum[i - 1];
printf ("%lld\n", ans);
memset (s, 0, sizeof s);
memset (c, 0, sizeof c);
memset (a, 0, sizeof a);
}
return 0;
}