暴力40pts
建立AC自动机
首先按照输入第一行模拟题意建立AC自动机,由于存在退回B操作,只需要在建立过程中记录一下父亲节点即可,并且记录一下第i个单词的末尾,这样就可以通过一直找爸爸的操作完整还原第$i$个字符串。
处理询问
对于第y个字符串,我们让其在AC自动机上跑一遍,然后对于每个节点暴力跳fail,当跳到第x字符串的结尾时记录个数,最终返回答案即可。
对于正常情况当Trie图建立后,遍历文本串每次都是跑到当前节点的儿子节点即正向遍历文本串,而改题目由于文本串肯定在Trie图中,由于在建立AC自动机过程中记录了父亲节点,只需要从第y个字符串的结尾位置一直找爸爸即逆向遍历文本串
如abbabb
正常情况:a—>ab—>abb—>abba—>abbab—>abbabb
本题情况:abbabb—>abbab—>abba—>abb—>ab—>a
时间复杂度:$O({|s|}+\sum{|t|}+10|t|^2)$
$|s|$表示输入第一行长度,$|t|$表示单个字符串的长度
对于前40pts,单个单词长度$\leq 10^3$,$m \leq 10^4$,总长度$\leq 10^5$,最爆炸的情况即询问10次,询问单个长度是$10^3$的单词,这样能够达到询问$10^7$量级,暴力能过
#include<queue>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
struct node
{
int chd[26],fa,fail;
}tree[N];
int cnt;
int pos[N],num,n;
void insert(string s)
{
int p=0;
for(int i=0;i<s.size();i++)
{
if(s[i]=='B') p=tree[p].fa;
else if(s[i]=='P') pos[++num]=p;//第num个单词的结尾是p
else
{
int c=s[i]-'a';
if(!tree[p].chd[c]) tree[p].chd[c]=++cnt,tree[cnt].fa=p;
p=tree[p].chd[c];
}
}
}
void build()
{
queue<int> q;
for(int i=0;i<26;i++)
if(tree[0].chd[i])
q.push(tree[0].chd[i]);
while(q.size())
{
int t=q.front();q.pop();
for(int i=0;i<26;i++)
{
int &chd=tree[t].chd[i];
if(chd)
tree[chd].fail=tree[tree[t].fail].chd[i],q.push(chd);
else
chd=tree[tree[t].fail].chd[i];
}
}
}
int query(int x,int y)
{
int res=0;
int now=pos[y];
while(now)
{
for(int i=now;i;i=tree[i].fail)//暴力跳fail
if(i==pos[x]) res++;
now=tree[now].fa;//找爸爸逆向遍历文本串
}
return res;
}
int main()
{
string s;
cin>>s;
insert(s);
build();
cin>>n;
for(int i=1;i<=n;i++)
{
int x,y;
cin>>x>>y;
cout<<query(x,y)<<'\n';
}
return 0;
}
70pts fail树+树状数组
默认已做过【模板】AC自动机(二次加强版)
对于上述暴力,主要是跳fail的时候会被链卡掉。
效仿上面模板题,只需要建立fail树,每次在到达某点后,它fail树上的祖先对应节点数也会+1,查询某点的值
树上的链加某个值+单点查询,即dfs序+树状数组 LOj模板题:DFS 序 3,树上差分 1
这样我们不需要暴力跳fail,而且当我们把相同的y放在一起后(不用每次在AC自动机上跑相同的文本串),只需要在跑该文本串前后统计一下次数即可做差求出答案。
时间复杂度$O(|s|+\sum{|t|}\log{|s|})$
#include<queue>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
struct node
{
int chd[26],fa,fail;
}tree[N];
int cnt;
int pos[N],num;
void insert(string s)
{
int p=0;
for(int i=0;i<s.size();i++)
{
if(s[i]=='B') p=tree[p].fa;
else if(s[i]=='P') pos[++num]=p;
else
{
int c=s[i]-'a';
if(!tree[p].chd[c]) tree[p].chd[c]=++cnt,tree[cnt].fa=p;
p=tree[p].chd[c];
}
}
}
void build()
{
queue<int> q;
for(int i=0;i<26;i++)
if(tree[0].chd[i])
q.push(tree[0].chd[i]);
while(q.size())
{
int t=q.front();q.pop();
for(int i=0;i<26;i++)
{
int &chd=tree[t].chd[i];
if(chd)
tree[chd].fail=tree[tree[t].fail].chd[i],q.push(chd);
else
chd=tree[tree[t].fail].chd[i];
}
}
}
int n;
int h[N],e[N],ne[N],idx;
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int dfn[N],sz[N],timestamp;
void dfs(int u)
{
if(u)
{
dfn[u]=++timestamp;
sz[u]=1;
}
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
dfs(j);
sz[u]+=sz[j];
}
}
int fw[N];
int lowbit(int x){return x&-x;}
void insert(int k,int x)
{
for(;k<=cnt;k+=lowbit(k))
fw[k]+=x;
}
int sum(int k)
{
int res=0;
for(;k;k-=lowbit(k))
res+=fw[k];
return res;
}
int query(int u)
{
return sum(dfn[u]+sz[u]-1)-sum(dfn[u]-1);
}
int ans[N];
struct node2
{
int x,y;
int id;
bool operator<(const node2& o)const
{
return y<o.y;
}
}q[N];
int main()
{
string s;
cin>>s;
insert(s);
build();
memset(h,-1,sizeof h);
for(int i=1;i<=cnt;i++)
add(tree[i].fail,i); //失配树
dfs(0);
cin>>n;
for(int i=1;i<=n;i++)
{
int x,y;
cin>>x>>y;
q[i]={x,y,i};
}
sort(q+1,q+1+n);
for(int i=1;i<=n;i++)
{
int j=i;
while(j<=n&&q[i].y==q[j].y) j++;
for(int k=i;k<j;k++)
ans[q[k].id]-=query(pos[q[k].x]);
for(int p=pos[q[i].y];p;p=tree[p].fa)
insert(dfn[p],1);
for(int k=i;k<j;k++)
ans[q[k].id]+=query(pos[q[k].x]);
i=j-1;
}
for(int i=1;i<=n;i++)
cout<<ans[i]<<'\n';
return 0;
}
正解100pts
这题有操作B,P的原因就是为了后面的30分做准备的,虽然第一行即输入是字符串的长度$\leq 10^5$,但是由于存在P操作,他会继承前面的字符导致所有出现的字符串总长度并不一定满足$\leq 10^5$这个条件。这是非常致命的,可能导致我们根本不能再AC自动机上跑一边询问的字符串,因为他们的总长太长导致即便线性也不能跑。
对于每一个文本串,我们都需要从该点末尾找爸爸找到根节点,也就是我们需要在Trie树上根节点到文本串末尾路径上的每个点对fail树进行操作,我们对不同的串会进行相同的步骤,非常耗费时间
如果首先统计有响应节点存在哪些询问,然后我们把Trie树按照建树的过程dfs遍历一遍,访问到的时候加上该点的贡献在fail树中打一个+1,结束的时候消去该点的贡献,在fail数中打一个-1,这样访问到某个节点是会把从这个节点到根节点上的所有点的贡献都会加上这样不用就每次寻找父亲了,然后效仿70pts的方法得出答案
时间复杂度$O(|s|+|s|\log{|s|})$
#include<queue>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
struct node
{
int chd[26],fa,fail;
}tree[N];
int cnt;
int pos[N],num;
void insert(string s)
{
int p=0;
for(int i=0;i<s.size();i++)
{
if(s[i]=='B') p=tree[p].fa;
else if(s[i]=='P') pos[++num]=p;
else
{
int c=s[i]-'a';
if(!tree[p].chd[c]) tree[p].chd[c]=++cnt,tree[cnt].fa=p;
p=tree[p].chd[c];
}
}
}
void build()
{
queue<int> q;
for(int i=0;i<26;i++)
if(tree[0].chd[i])
q.push(tree[0].chd[i]);
while(q.size())
{
int t=q.front();q.pop();
for(int i=0;i<26;i++)
{
int &chd=tree[t].chd[i];
if(chd)
tree[chd].fail=tree[tree[t].fail].chd[i],q.push(chd);
else
chd=tree[tree[t].fail].chd[i];
}
}
}
int n;
int h[N],e[N],ne[N],idx;
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int dfn[N],sz[N],timestamp;
void dfs(int u)
{
if(u)
{
dfn[u]=++timestamp;
sz[u]=1;
}
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
dfs(j);
sz[u]+=sz[j];
}
}
int fw[N];
int lowbit(int x){return x&-x;}
void insert(int k,int x)
{
for(;k<=cnt;k+=lowbit(k))
fw[k]+=x;
}
int sum(int k)
{
int res=0;
for(;k;k-=lowbit(k))
res+=fw[k];
return res;
}
int query(int u)
{
return sum(dfn[u]+sz[u]-1)-sum(dfn[u]-1);
}
int ans[N];
struct node2
{
int x,id;
};
vector<node2> adj[N];
int main()
{
string s;
cin>>s;
insert(s);
build();
memset(h,-1,sizeof h);
for(int i=1;i<=cnt;i++)
add(tree[i].fail,i); //失配树
dfs(0);
cin>>n;
for(int i=1;i<=n;i++)
{
int x,y;
cin>>x>>y;
adj[y].push_back({x,i});
}
int p=0;num=0;
for(int i=0;i<s.size();i++)
{
if(s[i]=='B')
{
insert(dfn[p],-1);
p=tree[p].fa;
}
else if(s[i]=='P')
{
++num;
for(auto t:adj[num])
ans[t.id]=query(pos[t.x]);
}
else
{
p=tree[p].chd[s[i]-'a'];
insert(dfn[p],1);
}
}
for(int i=1;i<=n;i++)
cout<<ans[i]<<'\n';
return 0;
}
这题在AcWing上这题难度竟然是中等,还是我太菜了
要加油哦~
牛
peter 银川站?
打不了,在学校太菜了,现在基本搞专业课了
牛
加油!!