这是我之前博客里提到的一道AC自动机的练手题&＃xff0c;但是要完成这道题&＃xff0c;我之前博客里提到的东西还不够&＃xff0c;这里总结一下这道题。
这道题不是一般的裸的AC自动机&＃xff0c;它的询问和插入是交叉出现的所以用我之前写的板子不大合适&＃xff0c;这道题在构建自动机时不能改变原有的 Trie树 的结构&＃xff0c;所以没有代表字符串的结点的不需要去改它的值&＃xff0c;所以我在 build() 函数 处做了一些修改。在复杂度方面&＃xff0c;如果是强上普通的AC自动机&＃xff0c;最差会达到O(n^2)&＃xff0c;感觉不太好。我们这里可以用到平方分割的套路&＃xff0c;搞大小两个自动机&＃xff0c;每次插入都在小自动机上进行&＃xff0c;当小自动机里的结点达到一定量&＃xff08;sqrt&＃xff08;n&＃xff09;&＃xff09;时&＃xff0c;就将两自动机合并&＃xff0c;并将小自动机清空。合并的方式也很好理解&＃xff0c;就将两个自动机的节点一一对应&＃xff0c;若小自动机上的结点在大自动机上没有&＃xff0c;就在大自动机上新建结点&＃xff0c;并修改它的值。总复杂度大概是这样&＃xff1a;O(n*sqrt(n)(小的)&＃43;O(sqrt(n)*n)(大的)&＃61;O(n*sqrt(n))。其实那个上界也不一定要严格的根号n&＃xff0c;自己大概估计一个常数就差不多了。哦对&＃xff0c;还有一点&＃xff0c;我发现好多板子里在构建新结点时都打了一个 newnode() 函数&＃xff0c;包括我自己的板子也是这么打的。这样打其实是很慢的&＃xff0c;我在做这道题时就各种 T飞 &＃xff0c;后来把这个去掉搞成其他的方法就快了很多(虽然我也不知道为什么)&＃xff0c;下面的代码里会体现。
祝大家切题愉快
#include
#include
#include
#include
#include
#include
#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&＃61;1; root&＃61;0;memset(son,0,sizeof(son));memset(val,0,sizeof(val));memset(fail,0,sizeof(fail));}il int idx(char c){ //卡常专用return c-&＃39;0&＃39;;}il int insert(char *s){ //插入新单词RG int cur&＃61;root;for(RG int i&＃61;0;s[i];i&＃43;&＃43;){ //卡常小技巧&＃xff0c;不要每次计算lenRG int id&＃61;idx(s[i]);if( !son[cur][id] ) son[cur][id]&＃61;size&＃43;&＃43;;cur&＃61;son[cur][id];}val[cur]&＃61;true;return cur;}il bool in(char *s){ //查询单词是否在自动机内RG int cur&＃61;root;for(RG int i&＃61;0;s[i];i&＃43;&＃43;){RG int id&＃61;idx(s[i]);if( !son[cur][id] ) return false;cur&＃61;son[cur][id];}return val[cur];}il void build(){ //构建自动机queue
}small,big;il void dfs(RG int u,RG int v){ //用于合并for(RG int i&＃61;0;i<2;i&＃43;&＃43;)if(small.son[v][i]){RG int cur2&＃61;small.son[v][i];if( !big.son[u][i] ){memset(big.son[big.size],0,sizeof(big.son[big.size]));big.son[u][i]&＃61;big.size&＃43;&＃43;; //建立新结点}RG int cur1&＃61;big.son[u][i];big.val[cur1] |&＃61;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&＃61;1;k<&＃61;Case;k&＃43;&＃43;){printf("Case #%d:\n",k);scanf("%d",&n);small.init(); big.init();RG int l&＃61;0;while(n--){scanf("%s",s);RG int len&＃61;strlen(s&＃43;1);ss[0]&＃61;s[0];for(RG int i&＃61;0;i
}
真是服了这鬼畜的缩进。。。真难看。。。
京公网安备 11010802041100号