HDU4787
来源
网上找的。
标签
根号分治 AC自动机
题意
给出两种操作：
· +w 表示学习一个新单词 \(w\)。
· ?p 表示询问段落 \(p\) 中有多少个子串是之前学习过的单词。
字符串仅包含0和1，强制在线，多组数据。
加密操作如下：
对于每个出现的字符串，设 \(lst\) 为上一个询问的结果。给定给你的字符串已经被移动了 \(lst\) 次（字符串 \(s1s2 ... sk\) 的移动版本是 \(sks1s2 ... sk-1\)）。
题解
首先我们明确在离线状态下我们如何处理操作。我们显然是可以通过AC自动机维护两种操作的。
插入操作等价于往AC自动机中插入一个新词。
对于询问操作。我们对于AC自动机上的每个节点维护一个信息 \(num[i]\) 表示通过该节点跳失配指针可以跳到多少单词节点。转移很容易，\(num[i]=num[fail[i]]+word[i]\)（\(word[i]\) 表示 \(i\) 是否为单词节点）。答案即为 \(\sum_{i=1}^{|s|} num[s[i]在AC自动机上对应的节点]\)。
但是在在线情况下我们每插入一个单词就需要花费 \(O(n)\) 的代价去重构失配树。
考虑根号重构。
我们用两个AC自动机来维护答案。小AC自动机维护当前的插入，每插入一个单词，我们就重构小AC自动机。当小AC自动机的大小大于 \(\sqrt{\sum|s|}\) 时，我们就将小AC自动机合并到大AC自动机中，并情况小AC自动机。答案即为两个AC自动机中的答案之和。
分析时间复杂度：
对于小AC自动机而言最多被清空 \(\sqrt{\sum|s|}\) 次，每次清空前最多重构 \(\sqrt{\sum|s|}\) 次，每次重构复杂度 \(O(\sqrt{\sum|s|})\)。总复杂度 \(O(\sum|s|\times\sqrt{\sum|s|})\)。
对于大AC自动机而言最多重构 \(\sqrt{\sum|s|}\) 次，每次重构复杂度 \(O(\sum|s|)\)。总复杂度 \(O(\sum|s|\times\sqrt{\sum|s|})\)。
整体复杂度 \(O(\sum|s|\times\sqrt{\sum|s|})\)。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int BL=330;
const int N=1e5+10;
int T,n,cnt,lst,cnt1,cnt2,ch1[N][2],ch2[N][2],fail1[N],fail2[N],num1[N],num2[N];
map<string,bool>mp;
bool f1[N],f2[N];
string s;
vector<string>v1;
vector<string>v2;
void clear1()
{
for(int i=0;i<=cnt1;i++)
{
memset(ch1[i],0,sizeof(ch1[i]));
fail1[i]=num1[i]=f1[i]=0;
}
cnt1=0;
return;
}
void clear2()
{
for(int i=0;i<=cnt2;i++)
{
memset(ch2[i],0,sizeof(ch2[i]));
fail2[i]=num2[i]=f2[i]=0;
}
cnt2=0;
return;
}
void insert1()
{
cnt=0;
clear1();
clear2();
v2.clear();
for(int i=0;i<v1.size();i++)
{
int len=v1[i].size()-1;
int z=0;
for(int j=1;j<=len;j++)
{
int to=v1[i][j]-'0';
if(ch1[z][to]==0)
ch1[z][to]=++cnt1;
z=ch1[z][to];
}
f1[z]=1;
num1[z]=1;
}
queue<int>q;
for(int i=0;i<=1;i++)
{
if(ch1[0][i]!=0)
{
q.push(ch1[0][i]);
}
}
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=0;i<=1;i++)
{
if(ch1[x][i]==0)
{
ch1[x][i]=ch1[fail1[x]][i];
}
else
{
fail1[ch1[x][i]]=ch1[fail1[x]][i];
q.push(ch1[x][i]);
num1[ch1[x][i]]+=num1[fail1[ch1[x][i]]];
}
}
}
return;
}
void insert2()
{
clear2();
for(int i=0;i<v2.size();i++)
{
int len=v2[i].size()-1;
int z=0;
for(int j=1;j<=len;j++)
{
int to=v2[i][j]-'0';
if(ch2[z][to]==0)
ch2[z][to]=++cnt2;
z=ch2[z][to];
}
f2[z]=1;
num2[z]=1;
}
queue<int>q;
for(int i=0;i<=1;i++)
{
if(ch2[0][i]!=0)
{
q.push(ch2[0][i]);
}
}
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=0;i<=1;i++)
{
if(ch2[x][i]==0)
{
ch2[x][i]=ch2[fail2[x]][i];
}
else
{
fail2[ch2[x][i]]=ch2[fail2[x]][i];
q.push(ch2[x][i]);
num2[ch2[x][i]]+=num2[fail2[ch2[x][i]]];
}
}
}
return;
}
void solve()
{
lst=0;
int z1=0,z2=0;
for(int i=1;i<=s.size()-1;i++)
{
int to=s[i]-'0';
z1=ch1[z1][to];
z2=ch2[z2][to];
lst+=num1[z1]+num2[z2];
}
cout<<lst<<'\n';
return;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>T;
for(int c_=1;c_<=T;c_++)
{
cout<<"Case #"<<c_<<":"<<'\n';
mp.clear();
lst=0,cnt=0;
v1.clear(),v2.clear();
clear1(),clear2();
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>s;
string r;
r+=s[0];
int rlst=lst%(s.size()-1);
for(int j=rlst+1;j<=s.size()-1;j++)
{
r+=s[j];
}
for(int j=1;j<=rlst;j++)
{
r+=s[j];
}
s=r;
if(s[0]=='+')
{
if(mp[s]==1)
continue;
mp[s]=1;
v1.push_back(s);
v2.push_back(s);
cnt+=s.size()-1;
if(cnt<BL)
insert2();
else
insert1();
}
else
{
solve();
}
}
}
return 0;
}
可能的出错点
1.插入的单词一定要去重，不然可能会分别被大小两个AC自动机计算到。
2.解密时需要将 \(lst\%|s|\) 不然会出问题。
3.要开longlong。
4.注意清空。
标签：AC,int,sum,sqrt,HDU4787,自动机,复杂度 From： https://www.cnblogs.com/hahaxiang/p/18105910