RT 算法效率觉得没问题 是 $n^2logn$的

不开O2 70pts 开了才能A

#include <bits/stdc++.h>

#define N 3010
#define M (int)(5e6+5)
#define ll long long
#define ull unsigned long long
#define base 212370440130137957
#define base2 1000000007
#define re register
#define il inline

using namespace std;

ull p[N],f[N],f2[N],p2[N];
char a[N],b[N];
int n,g[26][N],ct[26],cnt,ans;

struct node {
	int x,y;
}d[M];

il int gt(int l,int r) {
	return f[r]-f[l-1]*p[r-l+1];
}

il int gt2(int l,int r) {
	return f2[r]-f2[l-1]*p2[r-l+1];
}

il void solve(int l) {
	int no=0;
	for(re int i=l;i<=n;i++) {
		int u=*lower_bound(g[b[i]-'a'],g[b[i]-'a']+ct[b[i]-'a'],no+1);
		if(!u) break;
		else no=u;
		d[++cnt].x=gt(l,i); d[cnt].y=gt2(l,i); 
	}
}

bool cmp(node x,node y) {
	return x.x<y.x;
}

int main() {
	scanf("%d",&n); getchar(); scanf("%s",a+1); getchar(); scanf("%s",b+1);
	for(re int i=1;i<=n;i++) g[a[i]-'a'][ct[a[i]-'a']++]=i;
	p[0]=1; p2[0]=1;
	for(re int i=1;i<=n;i++) f[i]=f[i-1]*base+b[i],p[i]=p[i-1]*base;
	for(re int i=1;i<=n;i++) f2[i]=f2[i-1]*base2+b[i],p2[i]=p2[i-1]*base2;
	for(re int i=1;i<=n;i++) solve(i);
	sort(d+1,d+1+cnt,cmp);
	for(re int i=1;i<=cnt;i++) if(d[i].x!=d[i-1].x||d[i].y!=d[i-1].y) ++ans;
	printf("%d",ans);
}