Description
给定一个长度不超过 \(2 \times 10^3\) 的字符串,有 \(q \le 10^4\) 个询问,每个询问给出一个区间,问区间*有多少个不同的子串。
Solution
枚举一个后缀,增量构造 SAM,即可得到它所有子串中含有的不同子串的数目
在一次 sam.extend()
过程中,新增的本质不同子串数目为 \(len[last]-len[fa[last]]\),其中 \(cnt\) 是 \(endpos\) 集合的大小
#include <bits/stdc++.h>
using namespace std;
const int N = 4005;
struct SAM
{
int len[N], ch[N][26], fa[N], ind, last;
int t[N], a[N], cnt[N], f[N];
SAM()
{
ind = last = 1;
}
void clear()
{
memset(len,0,sizeof len);
memset(ch,0,sizeof ch);
memset(fa,0,sizeof fa);
memset(t,0,sizeof t);
memset(a,0,sizeof a);
memset(cnt,0,sizeof cnt);
memset(f,0,sizeof f);
ind = last = 1;
}
inline void extend(int id)
{
int cur = (++ ind), p;
len[cur] = len[last] + 1;
cnt[cur] = 1;
for (p = last; p && !ch[p][id]; p = fa[p]) ch[p][id] = cur;
if (!p) fa[cur] = 1;
else
{
int q = ch[p][id];
if (len[q] == len[p] + 1) fa[cur] = q;
else
{
int tmp = (++ ind);
len[tmp] = len[p] + 1;
for(int i=0; i<26; i++) ch[tmp][i] = ch[q][i];
fa[tmp] = fa[q];
for (; p && ch[p][id] == q; p = fa[p]) ch[p][id] = tmp;
fa[cur] = fa[q] = tmp;
}
}
last = cur;
}
int extend(char ch)
{
extend(ch-'a');
return len[last]-len[fa[last]];
}
} sam;
int ans[N/2][N/2];
void solve()
{
sam.clear();
string str;
cin>>str;
memset(ans,0,sizeof ans);
int m=str.length();
for(int i=1;i<=m;i++)
{
sam.clear();
for(int j=i;j<=m;j++)
{
ans[i][j]=ans[i][j-1]+sam.extend(str[j-1]);
}
}
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
int p,q;
cin>>p>>q;
cout<<ans[p][q]<<endl;
}
}
signed main()
{
ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--) solve();
}