题意:给一个2e4长的字符串 ,1e4次询问,每次询问一个区间内字符串的子串有多少种。
思路:字符串hash用来判重,之后dp预处理出每个区间的权值。复杂度On^2
值得总结的两点是:
- 为了使判重近似O1,可以如下不影响复杂度,通过%来解决,并且建链表。
判重之后这个问题就变成了给你1-n区间内所有子区间的权值,现在定义f(l,r)为区间[l,r]的所有子区间权值累加和怎么样On^2预处理出来。 - dp的预处理
因为计算任意一个点为左端点时一定要长度从小到大枚举,一个新的点可以由已知条件【l,r-1】构成,但是缺少了以r为右端点的情况。已知条件有【l+1,r】,再去重。因为是定左端点,所以一定要从子区间小的左端点枚举,所以n枚举到1。如果是定右端点,就可以枚举1到n了。
最后就有了这个kuangbin的板子
#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int maxn = 2005;
const int seed = 13331;
const int mod = 10007;
ull power[maxn],S[maxn];
int ans[maxn][maxn];
struct Hh{
int head[mod],nex[maxn],size,f[maxn];
ull state[maxn];
void init(){
size = 0;
memset(head,-1,sizeof(head));
}
int insert(ull v,int id){
int h = v%mod;
for(int i = head[h];i!=-1;i = nex[i]){
if(v==state[i]){
int x = f[i];
f[i] = id;
return x;
}
}
f[size] = id;
state[size] = v;
nex[size] = head[h];
head[h] = size++;
return 0;
}
}H;
int main(){
IO;int t;cin>>t;
power[0] = 1;
for1(i,maxn-1) power[i] = power[i-1]*seed;
while(t--){
string s;cin>>s;
int n = s.size();
for1(i,n) S[i] = S[i-1]*seed+s[i-1];
for1(i,n) for(int j = i;j<=n;j++) ans[i][j] = 1;
for1(i,n){
H.init();
for(int j = 1;j<=n-i+1;j++){
int l = H.insert(S[j+i-1]-S[j-1]*power[i],j);
ans[l][j+i-1]--;
}
}
for(int i = n;i>=1;i--){
for(int j = i+1;j<=n;j++){
ans[i][j] += ans[i+1][j]+ans[i][j-1]-ans[i+1][j-1];
}
}
int q;cin>>q;
while(q--){
int l,r;cin>>l>>r;
cout<<ans[l][r]<<'
';
}
}
return 0;
}