[HDU4787]GRE Words Revenge 解题报告
2024-09-23 19:17:39
这是我之前博客里提到的一道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; }
真是服了这鬼畜的缩进。。。真难看。。。
最新文章
- 如何调用外部的Web API
- Asp.Net MVC4 + Oracle + EasyUI 学习 第一章
- python连接数据库
- jade反编译
- java中文件的读取和写入
- CentOS生产机器禁止ROOT远程SSH登录
- CF:322D - Ciel and Duel 贪心 或者 DP 我用的贪心 。。难道sort跟qsort是不一样的么?
- ZOJ 2283 Challenge of Wisdom
- Interesting visualization tools for profiling.
- C# 关键字--using
- MarkDown换行
- JAVA数据结构之链表
- Petrozavodsk Winter Camp, Andrew, 2014, Bipartite Bicolored Graphs
- python闭包的详细解析
- BZOJ 4159 [Neerc2009]Business Center
- JDK7和JDK8concurrentHashmap区别
- C#利用zxing.net操作二维码和条形码
- linux——DNS服务器配置
- git 总结命令
- 写java代码有感。。。构造方法最好带着,
热门文章
- 在WebGL场景中管理多个卡牌对象的实验
- RabbitMQ入门:发布/订阅(Publish/Subscribe)
- Java SE练习题——求奇数
- 【坚持】Selenium+Python学习记录 DAY8
- Redis源码阅读(六)集群-故障迁移(下)
- 【神经网络】自编码聚类算法--DEC (Deep Embedded Clustering)
- 用线性分类器实现预测鸢尾花的种类(python)
- 8.openldap mirrormode(主主同步)
- dirname命令详解
- lambda----jdk8重头戏