这是我之前博客里提到的一道AC自动机的练手题，但是要完成这道题，我之前博客里提到的东西还不够，这里总结一下这道题。
这道题不是一般的裸的AC自动机，它的询问和插入是交叉出现的所以用我之前写的板子不大合适，这道题在构建自动机时不能改变原有的 Trie树 的结构，所以没有代表字符串的结点的不需要去改它的值，所以我在 build() 函数 处做了一些修改。在复杂度方面，如果是强上普通的AC自动机，最差会达到O(n^2)，感觉不太好。我们这里可以用到平方分割的套路，搞大小两个自动机，每次插入都在小自动机上进行，当小自动机里的结点达到一定量（sqrt（n））时，就将两自动机合并，并将小自动机清空。合并的方式也很好理解，就将两个自动机的节点一一对应，若小自动机上的结点在大自动机上没有，就在大自动机上新建结点，并修改它的值。总复杂度大概是这样：O(n*sqrt(n)(小的)+O(sqrt(n)*n)(大的)=O(n*sqrt(n))。其实那个上界也不一定要严格的根号n，自己大概估计一个常数就差不多了。哦对，还有一点，我发现好多板子里在构建新结点时都打了一个 newnode() 函数，包括我自己的板子也是这么打的。这样打其实是很慢的，我在做这道题时就各种 T飞 ，后来把这个去掉搞成其他的方法就快了很多(虽然我也不知道为什么)，下面的代码里会体现。
祝大家切题愉快
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#define maxn (511111)
#define N (6000000)
#define il inline
#define ll long long
#define RG register
using namespace std;
char s[N],ss[N];
struct Trie{
int son[maxn][2],fail[maxn],size,root;
bool val[maxn]; //标记是否出现
il void init(){
size=1; root=0;
memset(son,0,sizeof(son));
memset(val,0,sizeof(val));
memset(fail,0,sizeof(fail));
}
il int idx(char c){ //卡常专用
return c-'0';
}
il int insert(char *s){ //插入新单词
RG int cur=root;
for(RG int i=0;s[i];i++){ //卡常小技巧，不要每次计算len
RG int id=idx(s[i]);
if( !son[cur][id] ) son[cur][id]=size++;
cur=son[cur][id];
}
val[cur]=true;
return cur;
}
il bool in(char *s){ //查询单词是否在自动机内
RG int cur=root;
for(RG int i=0;s[i];i++){
RG int id=idx(s[i]);
if( !son[cur][id] ) return false;
cur=son[cur][id];
}
return val[cur];
}
il void build(){ //构建自动机
queue<int>Q;
for(RG int i=0;i<2;i++)
if( son[root][i] ) //只加入队列，不用修改值
Q.push(son[root][i]);
while(!Q.empty()){
RG int cur=Q.front(); Q.pop();
for(RG int i=0;i<2;i++){
RG int Son=son[cur][i];
if(!Son) continue;
Q.push(Son); //同上
RG int f=fail[cur];
while(f && !son[f][i] ) f=fail[f];
fail[Son]=son[f][i];
}
}
}
il int query(char *s){ //查询次数
RG int cur=root,ans=0;
for(RG int i=0;s[i];i++){
RG int id=idx(s[i]);
while(cur && !son[cur][id] ) cur=fail[cur];
cur=son[cur][id];
RG int k=cur;
while(k){
ans+=val[k];
k=fail[k];
}
}
return ans;
}
}small,big;
il void dfs(RG int u,RG int v){ //用于合并
for(RG int i=0;i<2;i++)
if(small.son[v][i]){
RG int cur2=small.son[v][i];
if( !big.son[u][i] ){
memset(big.son[big.size],0,sizeof(big.son[big.size]));
big.son[u][i]=big.size++; //建立新结点
}
RG int cur1=big.son[u][i];
big.val[cur1] |=small.val[cur2];
dfs(cur1,cur2);
}
}
il void join(){
dfs(0,0);
small.init();
big.build();
}
int main(){
RG int Case,n;
scanf("%d",&Case);
for(RG int k=1;k<=Case;k++){
printf("Case #%d:\n",k);
scanf("%d",&n);
small.init(); big.init();
RG int l=0;
while(n--){
scanf("%s",s);
RG int len=strlen(s+1);
ss[0]=s[0];
for(RG int i=0;i<len;i++)
ss[i+1]=s[ (i+l%len+len)%len+1 ];
ss[len+1]='\0';
if(ss[0]=='+'){
if( small.in(ss+1) || big.in(ss+1) ) continue;
//若该单词已经存在就跳过
small.insert(ss+1); small.build();
if( small.size>2333 ) join();
}
else{
l=small.query(ss+1)+big.query(ss+1);
printf("%d\n",l);
}
}
}
return 0;
}
真是服了这鬼畜的缩进。。。真难看。。。