正题
题目链接:https://www.luogu.com.cn/problem/P2414
题目大意
一个子串表示操作有
往凹槽里打一个字母删除最后一个字母将凹槽中的字母打印到一个新的行里（原来的不会消失）
然后每次询问两个数字
(
x
,
y
)
(x,y)
(x,y)表示询问第
x
x
x行的字串在第
y
y
y行的字串里出现了多少次
解题思路
考虑
A
C
AC
AC自动机上如何求子串关系，首先我们可以一个位置的
f
a
i
l
fail
fail指向的位置表示指向代表的串是该位置的串的后缀。所以我们可以发现一个询问
(
x
,
y
)
(x,y)
(x,y)其实就是询问
y
y
y这个串在
T
r
i
e
Trie
Trie上的所有点有多少的
f
a
i
l
fail
fail指针可以指向
x
x
x的结束位置。
然后可以在
f
a
i
l
fail
fail的指向反过来之后就成了一棵树，然后对于每个点会影响一段连续的区间，我们可以用树状数组维护即可
c
o
d
e
code
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#define lowbit(x) (x&-x)
using namespace std
;
const int N
=2e5+10;
struct node
{
int to
,next
;
}a
[N
*2];
int n
,m
,num
,tot
,cnt
,pos
[N
],ls
[N
],ans
[N
];
int t
[N
],fa
[N
],fail
[N
],dfn
[N
],ed
[N
],w
[N
];
int son
[N
][26],ch
[N
][26];
char s
[N
];
queue
<int> q
;
vector
<int> que
[N
];
void init(){
scanf("%s",s
);
int len
=strlen(s
),x
=0;
for(int i
=0;i
<len
;i
++){
if(s
[i
]=='B')x
=fa
[x
];
else if(s
[i
]=='P')
{pos
[++m
]=x
;}
else{
int c
=s
[i
]-'a';
if(!son
[x
][c
]){
son
[x
][c
]=++num
;
fa
[num
]=x
;
}
x
=son
[x
][c
];
}
}
return;
}
void Change(int x
,int val
){
while(x
<=cnt
){
t
[x
]+=val
;
x
+=lowbit(x
);
}
return;
}
int Ask(int x
){
int ans
=0;
while(x
){
ans
+=t
[x
];
x
-=lowbit(x
);
}
return ans
;
}
void addl(int x
,int y
){
a
[++tot
].to
=y
;
a
[tot
].next
=ls
[x
];
ls
[x
]=tot
;
return;
}
void get_fail(){
memcpy(ch
,son
,sizeof(ch
));
for(int i
=0;i
<26;i
++)
if(ch
[0][i
])q
.push(ch
[0][i
]);
while(!q
.empty()){
int x
=q
.front();q
.pop();
for(int i
=0;i
<26;i
++)
if(!ch
[x
][i
])ch
[x
][i
]=ch
[fail
[x
]][i
];
else{
q
.push(ch
[x
][i
]);
int y
=fail
[x
];
fail
[ch
[x
][i
]]=ch
[y
][i
];
}
}
for(int i
=1;i
<=num
;i
++)
addl(i
,fail
[i
]),addl(fail
[i
],i
);
return;
}
void dfs_fail(int x
,int fa
){
dfn
[x
]=++cnt
;
for(int i
=ls
[x
];i
;i
=a
[i
].next
){
int y
=a
[i
].to
;
if(y
==fa
)continue;
dfs_fail(y
,x
);
}
ed
[x
]=cnt
;
return;
}
void dfs_trie(int x
){
Change(dfn
[x
],1);
for(int i
=0;i
<que
[x
].size();i
++){
int pos
=que
[x
][i
];
ans
[pos
]=Ask(ed
[w
[pos
]])-Ask(dfn
[w
[pos
]]-1);
}
for(int i
=0;i
<26;i
++)
if(son
[x
][i
])
dfs_trie(son
[x
][i
]);
Change(dfn
[x
],-1);
return;
}
int main()
{
init();
get_fail();
scanf("%d",&n
);
for(int i
=1;i
<=n
;i
++){
int y
;
scanf("%d%d",&w
[i
],&y
);
que
[pos
[y
]].push_back(i
);
w
[i
]=pos
[w
[i
]];
}
dfs_fail(0,0);
dfs_trie(0);
for(int i
=1;i
<=n
;i
++)
printf("%d\n",ans
[i
]);
}
