题目背景
实力强大的小A 被选为了 ION2018 的出题人，现在他需要解决题目的命名问题。
题目描述
小A 被选为了 ION2018 的出题人，他精心准备了一道质量十分高的题目，且已经把除了题目命名以外的工作都做好了。
由于 ION 已经举办了很多届，所以在题目命名上也是有规定的， ION 命题手册规定：每年由命题委员会规定一个小写字母字符串，我们称之为那一年的命名串，要求每道题的名字必须是那一年的命名串的一个非空连续子串，且不能和前一年的任何一道题目的名字相同。
由于一些特殊的原因，小A 不知道 ION2017 每道题的名字，但是他通过一些特殊手段得到了 ION2017 的命名串，现在小A 有 Q 次询问：每次给定 ION2017 的命名串和 ION2018 的命名串，求有几种题目的命名，使得这个名字一定满足命题委员会的规定，即是 ION2018 的命名串的一个非空连续子串且一定不会和 ION2017 的任何一道题目的名字相同。
由于一些特殊原因，所有询问给出的 ION2017 的命名串都是某个串的连续子串，详细可见输入格式。
输入和输出
输入格式
第一行一个字符串 S，之后询问给出的 ION2017 的命名串都是 S 的连续子串。 第二行一个正整数 Q，表示询问次数。 接下来 Q 行，每行有一个字符串 T 和两个正整数 $l,r$，表示询问如果 ION2017 的 命名串是 $S [l..r]$， ION2018 的命名串是 T 的话，有几种命名方式一定满足规定。
输出格式
输出Q 行，第 i 行一个非负整数表示第 i 个询问的答案。
样例
输入
scbamgepe
3
smape 2 7
sbape 3 8
sgepe 1 9输出
12
10
4数据范围和提示
| 测试点 | $∣S∣≤$ | $Q≤$ | $∑∣T∣≤$ | 其他限制 |
|---|---|---|---|---|
| 1 | $200$ | $200$ | $40000$ | $∣T∣≤200$ |
| 2 | $1000$ | $200$ | $40000$ | $∣T∣≤200$ |
| 3 | $1000$ | $200$ | $40000$ | $∣T∣≤200$ |
| 4 | $1000$ | $200$ | $5×10^5$ | 无 |
| 5 | $1000$ | $200$ | $5×10^5$ | 无 |
| 6 | $5×10^5$ | $1$ | $5×10^5$ | 无 |
| 7 | $5×10^5$ | $1$ | $5×10^5$ | 无 |
| 8 | $10^5$ | $10^5$ | $2×10^5$ | 无 |
| 9 | $10^5$ | $10^5$ | $2×10^5$ | 字符串随机 |
| 10 | $2×10^5$ | $10^5$ | $4×10^5$ | 无 |
| 11 | $2×10^5$ | $10^5$ | $4×10^5$ | 字符串随机 |
| 12 | $3×10^5$ | $10^5$ | $6×10^5$ | 无 |
| 13 | $3×10^5$ | $10^5$ | $6×10^5$ | 字符串随机 |
| 14 | $4×10^5$ | $10^5$ | $8×10^5$ | 无 |
| 15 | $4×10^5$ | $10^5$ | $8×10^5$ | 字符串随机 |
| 16 | $5×10^5$ | $10^5$ | $10^6$ | 无 |
| 17 | $5×10^5$ | $10^5$ | $10^6$ | 字符串随机 |
| 18 | $2×10^5$ | $10^5$ | $10^6$ | 无 |
| 19 | $3×10^5$ | $10^5$ | $10^6$ | 无 |
| 20 | $4×10^5$ | $10^5$ | $10^6$ | 无 |
| 21 | $5×10^5$ | $10^5$ | $10^6$ | 无 |
| 22 | $5×10^5$ | $10^5$ | $10^6$ | 无 |
| 23 | $5×10^5$ | $10^5$ | $10^6$ | 无 |
| 24 | $5×10^5$ | $10^5$ | $10^6$ | 无 |
| 25 | $5×10^5$ | $10^5$ | $10^6$ | 无 |
思路
我们考虑求 $T$ 的一个前缀在 $S[l,r]$ 中能匹配的最长后缀。
首先我们需要对$T$和$S$分别建立 SAM，然后我们考虑对 $T$ 的一个前缀不断加入新字符。在 $S$ 的 parent 树里，如果当前状态存在一条到新插入字符的边，新状态合法，就说明新状态在 parent 树的子树中存在至少一个前缀结点，其深度在 $[l+l’,r]$ 之间。
所以我们只需要再用主席树对 DFS序 维护一下深度即可。
答案计数到 i 的时候的 $max(0,dep[i]-max(dep[fa[i]],lim))$ 也很好理解了是不是哇。
╰(￣ω￣ｏ)
代码
// name.cpp : Defines the entry point for the console application.
// XG_Zepto, 7/25/2018. All rights reserved.
#include
#include
#include
#include
#define maxn 1000005
#define mid ((l+r)>>1)
#define ll long long
using namespace std;
struct Edge {
int to,next;
Edge(int a=0,int b=0){
to=a,next=b;
}
};
struct President_Tree{
int tree[maxn<<4],ls[maxn<<4],rs[maxn<<4],cnt;
void update(int &now,int pre,int l,int r,int x){
now=++cnt;
tree[now]=tree[pre]+1;
if (l==r) return;
if (x<=mid) rs[now]=rs[pre],update(ls[now],ls[pre],l,mid,x);
else ls[now]=ls[pre],update(rs[now],rs[pre],mid+1,r,x);
}
int query(int now,int l,int r,int L,int R){
if (!now) return 0;
if (l>=L&&r<=R) return tree[now];
int res=0;
if (mid>=L) res+=query(ls[now],l,mid,L,R);
if (mid>1];
int lst,ct,nl,mp[maxn][27],fa[maxn],dep[maxn],pre[maxn],cte;
int head[maxn],pos[maxn],root[maxn],frt[maxn],sed[maxn],dfn;
SAMS(){lst=ct=1;}
void add(int a,int b){
l[++cte]=Edge(b,head[a]);
head[a]=cte;
}
void expand(int i){
int c=s[i]-'a'+1,p=ct,np=++ct;
dep[np]=dep[lst]+1;
pre[np]=true;
for(p=lst;p&&!mp[p][c];p=fa[p]) mp[p][c]=np;
if(!p){
fa[np]=1;
lst=np;
return;
}
int q=mp[p][c];
if(dep[q]==dep[p]+1){
fa[np]=q;
lst=np;
return;
}
int nq=++ct;
dep[nq]=dep[p]+1;
fa[nq]=fa[q];
for(int j=1;j<=26;j++) mp[nq][j]=mp[q][j];
fa[q]=fa[np]=nq;
for(;p&&mp[p][c]==q;p=fa[p])mp[p][c]=nq;
lst=np;
}
void dfs(int u){
frt[u]=++dfn;
pos[dfn]=u;
for (int i=head[u];i;i=l[i].next)
dfs(l[i].to);
sed[u]=dfn;
}
void build(){
nl=strlen(s+1);
for (int i=1;i<=nl;i++) expand(i);
for (int i=2;i<=ct;i++) add(fa[i],i);
dfs(1);
for (int i=1;i<=dfn;i++){
if (pre[pos[i]]) pt.update(root[i],root[i-1],1,nl,dep[pos[i]]);
else root[i]=root[i-1];
}
}
bool valid(int x,int l,int r){
return x&&pt.query(root[sed[x]],1,nl,l,r)>pt.query(root[frt[x]-1],1,nl,l,r);
}
}S;
char t[maxn];
int lst,ct,m,mp[maxn<<1][27],fa[maxn<<1],dep[maxn<<1],pos[maxn<<1],lim[maxn<<1];
void expand(int i){
int c=t[i]-'a'+1,p=ct,ed=++ct;
dep[ed]=dep[lst]+1;
pos[ed]=i;
for(p=lst;p&&!mp[p][c];p=fa[p]) mp[p][c]=ed;
if(!p){
fa[ed]=1;
lst=ed;
return;
}
int q=mp[p][c];
if(dep[q]==dep[p]+1){
fa[ed]=q;
lst=ed;
return;
}
int nq=++ct;
dep[nq]=dep[p]+1;
fa[nq]=fa[q];
pos[nq]=pos[q];
for(int j=1;j<=26;j++) mp[nq][j]=mp[q][j];
fa[q]=fa[ed]=nq;
for(;p&&mp[p][c]==q;p=fa[p]) mp[p][c]=nq;
lst=ed;
}
int main(){
scanf("%s",S.s+1);
S.build();
int Q;
scanf("%d",&Q);
while(Q--){
int l,r,nowl=0,p=1;
scanf("%s%d%d",t+1,&l,&r);
m=strlen(t+1);
lst=ct=1;
for (int i=1;i<=m;i++){
expand(i);
while(1){
if(S.valid(S.mp[p][t[i]-'a'+1],l+nowl,r)){
nowl++;
p=S.mp[p][t[i]-'a'+1];
break;
}
if (!nowl) break;
nowl--;
if (nowl==S.dep[S.fa[p]]) p=S.fa[p];
}
lim[i]=nowl;
}
ll ans=0;
for (int i=2;i<=ct;i++)
ans+=max(0,dep[i]-max(dep[fa[i]],lim[pos[i]]));
printf("%lld
",ans);
for (int i=1;i<=ct;i++)
for (int j=1;j<=26;j++)
mp[i][j]=0;
}
return 0;
}