我不会字符串.jpg
我们现在求的是 AABCAB 的出现次数。
我们优先统计这个 ABCAB，写个 \(lcp_{i,j}\) ，表示 \(i\) 到 \(n\) 和 \(j\) 到 \(n\) 字符串的最长公共前缀。
我们现在枚举这个 AB 的出现位置，一个记作 \(i\),一个记作 \(j\)，这两个所构成的 AB 的长度是在 \(\min(j-i-1,lcp_{i,j})\) 区间内的，直接枚举其长度并设为 \(l_1\)。
现在我们只有一个 A 的长度不知道了，我们继续枚举它的长度 \(l_2<l_1\)，现在就可以计算答案了。
\(\sum_{i=1}^n \sum_{j=i+1}^n \sum_{l_2=2}^{\min(j-i-1,lcp_{i,j})} \sum_{l_1=1}^{l_2-1} [lcp_{i-l_1,i} \geq l_1]\)
这个 \(i,j\) 省略不掉了，我们考虑优化后面那一坨，直接提出来，记 \(mn=\min(j-i-1,lcp_{i,j})\)，现在就是要优化下面这个式子：
\(\sum_{l_2=2}^{mn} \sum_{l_1=1}^{l_2-1} [lcp_{i-l_1,i} \geq l_1]\)
于是化掉这个 \(l_2\)，现在变成了， \(\sum_{l_1=1}^{mn-1} [lcp_{i-l_1,i} \geq l_1](mn-l_1)\)。
注意到这个只与 \(mn,i\) 有关，你可以对于每个 \(i,mn\) 用个 \(n^2\) 预处理掉就行了。
预处理的方式就是先求出 \([lcp_{i-1,i} \geq 1] + [lcp_{i-2,i} \geq 2]...+[lcp_{1,i} \geq i-1]\)。
这个时候你再做一遍前缀和就有我们要的东西了。
这个还算显然 (?)。
#include<bits/stdc++.h>
using namespace std;
int n,m,f[5011][5011],t;
long long ans,sm[5011][5011],ys[5011][5011];
string s;
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// freopen("repeat.in", "r", stdin);
// freopen("repeat.out", "w", stdout);cin>>t;while(t--){cin>>s;n=s.size();s=" "+s;memset(f,0,sizeof f);ans=0;for(int i=n;i>=1;i--){for(int j=n;j>=1;j--){if(s[i]==s[j]) f[i][j]=f[i+1][j+1]+1;}}for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){sm[i][j]=sm[i][j-1]+(f[i-j][i]>=j);}for(int j=i+1;j<=n;j++) sm[i][j]=sm[i][j-1];for(int j=1;j<=n;j++){ys[i][j]=ys[i][j-1]+sm[i][j];}}for(int i=2;i<=n;i++){for(int j=i+3;j<n;j++){int mn=min(f[i][j],j-i-1);if(mn<2) continue;ans=ans+ys[i][mn-1];}} cout<<ans<<"\n";}return 0;
}