hdoj5769后缀自动机版本

时间:2022-08-27 14:29:08

网上的题解都是后缀数组,我来个后缀自动机题解。

建好后缀自动机后由于后缀自动机是单向的,那么dfs一遍记录各节点的size,要保证一个节点只经过一次才是O(n),否则是O(n^2)。表示这个节点及后面还有几个节点。然后再来个ans数组,再dfs一次。这次如果走的是题目要的字母(记c),那么ans[x]+=siz[to],因为to能到的节点对应的子串都有c。如果走的不是c,那么ans[x]+=ans[to]。ans其实就表示该节点以后能有几个能有c的子串。同样ans只能走一次,否则是n^2的。那么开始时memset为-1。走到一个节点就赋为0。这样-1的点就是还需要dfs的,一个点只走一次。具体看两个dfs函数。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cstring>
#include <map>
#include <queue>
#include <set>
#include <cassert>
#include <stack>
#include <bitset>
#define mkp make_pair
using namespace std;
const double EPS=1e-;
typedef long long lon;
const lon SZ=,SSZ=*SZ,APB=,INF=0x7FFFFFFF,mod=;
lon cnt,maxlen[SSZ],minlen[SSZ],nex[SSZ][APB];
lon slink[SSZ],siz[SSZ],ans[SSZ];
char dst,ch[SZ]; lon add(lon pre,lon c)
{
lon z=++cnt;
maxlen[z]=maxlen[pre]+;
lon u=pre;
for(;u!=-&&!nex[u][c];u=slink[u])
{
nex[u][c]=z;
}
if(u==-)
{
slink[z]=;
minlen[z]=;
}
else
{
lon x=nex[u][c];
if(maxlen[x]==maxlen[u]+)
{
slink[z]=x;
minlen[z]=maxlen[slink[z]]+;
}
else
{
lon v=++cnt;
memcpy(nex[v],nex[x],sizeof(nex[x]));
slink[v]=slink[x];
maxlen[v]=maxlen[u]+;
minlen[v]=maxlen[slink[v]]+;
slink[x]=slink[z]=v;
minlen[x]=maxlen[slink[x]]+;
minlen[z]=maxlen[slink[z]]+;
for(;u!=-&&nex[u][c]==x;u=slink[u])
{
nex[u][c]=v;
}
}
}
return z;
} void init()
{
scanf(" %c",&dst);
scanf(" %s",ch+);
lon pre=;
slink[]=-;
cnt=;
memset(ans,-,sizeof(ans));
for(lon i=;ch[i];++i)
{
pre=add(pre,ch[i]-'a');
}
} void dfs1(lon x)
{
siz[x]=;
for(lon i=;i<APB;++i)
{
lon t=nex[x][i];
if(t)
{
if(!siz[t])dfs1(t);
siz[x]+=siz[t];
}
}
} void dfs2(lon x)
{
ans[x]=;
for(lon i=;i<APB;++i)
{
lon t=nex[x][i];
if(t)
{
if(ans[t]==-)dfs2(t);
if(i==dst-'a')ans[x]+=siz[t];
else ans[x]+=ans[t];
}
}
} void work()
{
dfs1();
dfs2();
cout<<ans[]<<endl;
for(int i=;i<=cnt;++i)
{
memset(nex[i],,sizeof(nex[i]));
siz[i]=;
}
} int main()
{
//std::ios::sync_with_stdio(0);
//freopen("d:\\1.txt","r",stdin);
lon casenum;
cin>>casenum;
//cout<<casenum<<endl;
for(lon time=;time<=casenum;++time)
//for(lon time=1;cin>>n>>len>>wid;++time)
{
cout<<"Case #"<<time<<": ";
init();
work();
}
return ;
}

hdoj5769后缀自动机版本的更多相关文章

  1. 后缀自动机(SAM)学习笔记

    目录 定义 SAM 的状态集 一些性质 SAM 的后缀链接 SAM 的转移函数 一些性质 算法构造 构造方法 时间复杂度证明 状态的数量 转移的数量 代码实现 实际应用 统计本质不同的子串个数 计算任 ...

  2. SPOJ8093Sevenk Love Oimaster(广义后缀自动机)

    Oimaster and sevenk love each other.     But recently,sevenk heard that a girl named ChuYuXun was da ...

  3. 后缀自动机SAM BZOJ 2806

    终于遇到了一道后缀数组不能过 一定要学SAM的题... (看了半个下午+半个上午) 现在总结一下(是给我自己总结..所以只总结了我觉得重要的 .. 看不太懂的话可以To   http://blog.c ...

  4. CF547E Milk and Friends&lpar;AC自动机的fail指针上建主席树 或 广义后缀自动机的parent线段树合并&rpar;

    What-The-Fatherland is a strange country! All phone numbers there are strings consisting of lowercas ...

  5. 【洛谷4482】Border的四种求法(后缀自动机&lowbar;线段树合并&lowbar;链分治)

    这题我写了一天后交了一发就过了我好兴奋啊啊啊啊啊啊 题目 洛谷 4482 分析 这题明明可以在线做的,为什么我见到的所有题解都是离线啊 -- 什么时候有机会出一个在线版本坑人. 题目的要求可以转化为求 ...

  6. 一文读懂后缀自动机 Suffix&lowbar;Automata

    原论文(俄文)地址:suffix_automata 原翻译(中文)地址:后缀自动机详解(DZYO的博客) Upd:强推浅显易懂(?)的SAM讲解 后缀自动机 后缀自动机(单词的有向无环图)--是一种强 ...

  7. 『后缀自动机入门 SuffixAutomaton』

    本文的图片材料多数来自\(\mathrm{hihocoder}\)中详尽的\(SAM\)介绍,文字总结为原创内容. 确定性有限状态自动机 DFA 首先我们要定义确定性有限状态自动机\(\mathrm{ ...

  8. 后缀自动机&lpar;SAM&rpar;奶妈式教程

    后缀自动机(SAM) 为了方便,我们做出如下约定: "后缀自动机" (Suffix Automaton) 在后文中简称为 SAM . 记 \(|S|\) 为字符串 \(S\) 的长 ...

  9. BZOJ 后缀自动机四&&num;183&semi;重复旋律7

    后缀自动机四·重复旋律7 时间限制:15000ms 单点时限:3000ms 内存限制:512MB 描述 小Hi平时的一大兴趣爱好就是演奏钢琴.我们知道一段音乐旋律可以被表示为一段数构成的数列. 神奇的 ...

随机推荐

  1. java中Array&sol;List&sol;Map&sol;Object与Json互相转换详解

    http://blog.csdn.net/xiaomu709421487/article/details/51456705 JSON(JavaScript Object Notation): 是一种轻 ...

  2. &lbrack;转&rsqb;jquery 对 Json 的各种遍历

    原文地址:http://caibaojian.com/jquery-each-json.html 概述 JSON(javascript Object Notation) 是一种轻量级的数据交换格式,采 ...

  3. &period;NET之委托

    有些.NET中的高级特性,比如:委托! 有一种怎么也搞不懂的赶脚... 博客读了好几篇,代码也动手写了,书中的一些介绍也看了, 各种搜索关于委托的,至今还处于"会用"的阶段. 该怎 ...

  4. c显示数字的LED(数字转LED)

    实现这么一个函数:传入一个int值,在屏幕输出类似LED显示屏效果的字母拼图,例如: 输入1234567890,输出: 请注意每个字符的固定宽度和高度,两个数字间保留一个空格. 函数名:void LE ...

  5. Qt中利用QTime类来控制时间&comma;这里简单介绍一下QTime的成员函数的用法&colon;

    Qt中利用QTime类来控制时间,这里简单介绍一下QTime的成员函数的用法: ------------------------------------------------------------ ...

  6. MicroPython开发板:TPYBoard v102 播放音乐实例

    0x00前言 前段时间看到TPYBoard的技术交流群(群号:157816561,)里有人问关于TPYBoard播放音乐的问题.最近抽空看了一下文档介绍,着手做了个实验.更多MicroPython的教 ...

  7. FreeMarker案例

  8. RBAC 权限设计(转载)

    来源 :https://blog.csdn.net/rocher88/article/details/43190743 这是我在网上找的一些设计比较好的RBAC权限管理 不知道,像新浪.搜狐.网易.百 ...

  9. 黄聪:保持web页面生成的app一直处于用户登录状态不退出

    用户登录了会员中心,怎么保持登录状态! 由于封壳的内核及组件肯定没有浏览器APP应用那么强大,所以目前暂时的解决方案是: jquery.cookie.js  本文转载至:https://www.cnb ...

  10. js 变量提升(JavaScript Scoping and Hoisting)

    原文网址:http://www.cnblogs.com/betarabbit/archive/2012/01/28/2330446.html 这是一篇作者翻译过来的文章,未翻译的原文网址在这里:htt ...