[NOIP2020] 字符串匹配
枚举两个分界点并检查是否合法的暴力很显然，考虑优化。
字符串只会哈希可以想到用哈希优化比较复杂度，具体来说，只用枚举\(AB\)的长度\(len\)，然后每次暴力往后跳用哈希检查往下\(len\)个字符并更新答案，直到它们与\(AB\)不同。
同时考虑如何统计\(f(A) \leq f(C)\)的对数，显然前缀后缀的\(f\)都可以线性预处理，用树状数组维护小于\(f(C)\)的前缀个数即可。
由调和级数可知时间复杂度\(O(n \log_2 n \log_2 26)\)，需要轻微卡常。
说得有点抽象，直接看代码吧。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int T;
const int MAXN=1050000;
#define ull unsigned long long
ull mul[MAXN];
ull P=131;
struct Hash{
ull H[MAXN];
void init(char *s,int n){
for (int i=1;i<=n;i++){
H[i]=H[i-1]*P+(s[i]-'a'+1);
}
}
ull hash(int l,int r){
return H[r]-H[l-1]*mul[r-l+1];
}
}h;
int n;
char s[MAXN];
struct Bit{
int bit[30];
#define lowbit(x) (x&(-x))
void update(int p,int v){
p++;
for (;p<=27;p+=lowbit(p)) bit[p]+=v;
}
int query(int p){
p++;
int ret=0;
for (;p;p-=lowbit(p)) ret+=bit[p];
return ret;
}
void clear(){
for (int i=0;i<30;i++) bit[i]=0;
}
#undef lowbit
}t;
int f1[MAXN],f2[MAXN],cnt[30],res;
void prework(){
memset(cnt,0,sizeof cnt);res=0;
for (int i=1;i<=n;i++){
if (cnt[s[i]-'a'+1]&1) res--;
cnt[s[i]-'a'+1]++;
if (cnt[s[i]-'a'+1]&1) res++;
f1[i]=res;
}
memset(cnt,0,sizeof cnt);res=0;
for (int i=n;i;i--){
if (cnt[s[i]-'a'+1]&1) res--;
cnt[s[i]-'a'+1]++;
if (cnt[s[i]-'a'+1]&1) res++;
f2[i]=res;
}
}
#define ll long long
int main(){
mul[0]=1;
for (int i=1;i<MAXN;i++) mul[i]=mul[i-1]*P;
cin>>T;
while(T--){
scanf("%s",(s+1));n=strlen(s+1);
h.init(s,n);
prework();
t.clear();
ll ans=0;
t.update(f1[1],1);
for (int len=2;len<n;len++){
int k;
for (k=len+1;k+len-1<n;k+=len){
if (h.hash(1,len)!=h.hash(k,k+len-1)) break;
ans+=t.query(f2[k]);
}
ans+=t.query(f2[k]);
t.update(f1[len],1);
}
printf("%lld\n",ans);
}
return 0;
}