70%

预处理出哈希时每一个数位上的位权，以及原串的前缀哈希值。对于每次询问可以枚举询问区间内的所有子串，用字符串哈希判断重复即可，复杂度$O(qn^2)$

100%

问题瓶颈在于询问，考虑预处理所有区间的答案，通过求出每个子串对答案的贡献来得到，记$ans[i][j]$表示$[i,j]$及其子区间内本质不同的子串个数，考虑每个子串有贡献的是连续的一系列区间，可以先维护差分数组（$ans[i][j]$表示串$[i,j]$是否构成本质不同的子串个数）再求和得到区间内本质不同的子串个数。

先枚举子串长度，再枚举左端点，通过预处理的前缀和求出这 $[i,j]$ 一子串的哈希值，那么该串的左右端点$ans[i][j]$的答案加一，即$ans[i][j]++$，为了避免重复统计，该串还在上次该串出现位置到该位置之间该串都有贡献，那么应该将上一次出现的左端点$x$（字符串哈希维护）与当前右端点的答案减一，即$ans[x][j]--$，最后对数组求和得到的其实是会有重复贡献，要通过容斥计算出每个区间的答案$ans[i][j]$，回答询问。

复杂度$O(n^2+q)$

「关于hash冲突」

建议用自然溢出来代替hash中的取模操作，自然溢出比取模效率更好，也更容易减少冲突。

但实际上，也有专门的构造方法卡自然溢出，此时可以用多关键字哈希。

#include<bits/stdc++.h>
using namespace std;

const int maxn=3000 +5,base = 233333;
int n,q;
char s[maxn];
unsigned long long ha[maxn],mi[maxn];
int ans[maxn][maxn];
unsigned long long H(int l,int r){
	return ha[r]-ha[l-1]*mi[r -l+1];
}
unordered_map<unsigned long long,int>mp; //记录最近一次该类字串的出现左端点
int main(){
    freopen("substring.in", "r", stdin);
    freopen("substring.out", "w", stdout);
    scanf("%d%d",&n,&q);
    scanf("%s",s+1);
    mi[0]= 1;
    for(int i=1;i<=n; i++)ha[i]=ha[i-1]* base + s[i],mi[i]= mi[i - 1]* base;
        for(int len=1;len<= n;len++){
        mp.clear();
        for(int l=1;l+len-1<= n; l++){
            int r=l+len-1;
            unsigned long long tmp=H(l,r);
            ans[mp[tmp]][r]--;
            mp[tmp]=l;
        }
    }
    for(int l=n;l>=1;l--)
    	for (int r =l;r <=n; r++)
    		ans[l][r]+= ans[l+ 1][r]+ans[l][r-1]-ans[l+ 1][r - 1]+ 1;
    		//+1显然是[l,r]串
    		// ans[l+1][r]+ans[l][r-1]-ans[l+1][r-1]还剩 前缀与后缀相同且[l,r]中只有这两个 的部分算重了而没减
    for(int i=1,l,r;i<=q; i++){
        scanf("%d%d",&l,&r);
        printf("%d\n", ans[l][r]);
    }
    return 0;
}

考察知识点

贡献 二维前缀和