网上的题解都是后缀数组,我来个后缀自动机题解。
建好后缀自动机后由于后缀自动机是单向的,那么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后缀自动机版本的更多相关文章
-
后缀自动机(SAM)学习笔记
目录 定义 SAM 的状态集 一些性质 SAM 的后缀链接 SAM 的转移函数 一些性质 算法构造 构造方法 时间复杂度证明 状态的数量 转移的数量 代码实现 实际应用 统计本质不同的子串个数 计算任 ...
-
SPOJ8093Sevenk Love Oimaster(广义后缀自动机)
Oimaster and sevenk love each other. But recently,sevenk heard that a girl named ChuYuXun was da ...
-
后缀自动机SAM BZOJ 2806
终于遇到了一道后缀数组不能过 一定要学SAM的题... (看了半个下午+半个上午) 现在总结一下(是给我自己总结..所以只总结了我觉得重要的 .. 看不太懂的话可以To http://blog.c ...
-
CF547E Milk and Friends(AC自动机的fail指针上建主席树 或 广义后缀自动机的parent线段树合并)
What-The-Fatherland is a strange country! All phone numbers there are strings consisting of lowercas ...
-
【洛谷4482】Border的四种求法(后缀自动机_线段树合并_链分治)
这题我写了一天后交了一发就过了我好兴奋啊啊啊啊啊啊 题目 洛谷 4482 分析 这题明明可以在线做的,为什么我见到的所有题解都是离线啊 -- 什么时候有机会出一个在线版本坑人. 题目的要求可以转化为求 ...
-
一文读懂后缀自动机 Suffix_Automata
原论文(俄文)地址:suffix_automata 原翻译(中文)地址:后缀自动机详解(DZYO的博客) Upd:强推浅显易懂(?)的SAM讲解 后缀自动机 后缀自动机(单词的有向无环图)--是一种强 ...
-
『后缀自动机入门 SuffixAutomaton』
本文的图片材料多数来自\(\mathrm{hihocoder}\)中详尽的\(SAM\)介绍,文字总结为原创内容. 确定性有限状态自动机 DFA 首先我们要定义确定性有限状态自动机\(\mathrm{ ...
-
后缀自动机(SAM)奶妈式教程
后缀自动机(SAM) 为了方便,我们做出如下约定: "后缀自动机" (Suffix Automaton) 在后文中简称为 SAM . 记 \(|S|\) 为字符串 \(S\) 的长 ...
-
BZOJ 后缀自动机四&#183;重复旋律7
后缀自动机四·重复旋律7 时间限制:15000ms 单点时限:3000ms 内存限制:512MB 描述 小Hi平时的一大兴趣爱好就是演奏钢琴.我们知道一段音乐旋律可以被表示为一段数构成的数列. 神奇的 ...
随机推荐
-
java中Array/List/Map/Object与Json互相转换详解
http://blog.csdn.net/xiaomu709421487/article/details/51456705 JSON(JavaScript Object Notation): 是一种轻 ...
-
[转]jquery 对 Json 的各种遍历
原文地址:http://caibaojian.com/jquery-each-json.html 概述 JSON(javascript Object Notation) 是一种轻量级的数据交换格式,采 ...
-
.NET之委托
有些.NET中的高级特性,比如:委托! 有一种怎么也搞不懂的赶脚... 博客读了好几篇,代码也动手写了,书中的一些介绍也看了, 各种搜索关于委托的,至今还处于"会用"的阶段. 该怎 ...
-
c显示数字的LED(数字转LED)
实现这么一个函数:传入一个int值,在屏幕输出类似LED显示屏效果的字母拼图,例如: 输入1234567890,输出: 请注意每个字符的固定宽度和高度,两个数字间保留一个空格. 函数名:void LE ...
-
Qt中利用QTime类来控制时间,这里简单介绍一下QTime的成员函数的用法:
Qt中利用QTime类来控制时间,这里简单介绍一下QTime的成员函数的用法: ------------------------------------------------------------ ...
-
MicroPython开发板:TPYBoard v102 播放音乐实例
0x00前言 前段时间看到TPYBoard的技术交流群(群号:157816561,)里有人问关于TPYBoard播放音乐的问题.最近抽空看了一下文档介绍,着手做了个实验.更多MicroPython的教 ...
- FreeMarker案例
-
RBAC 权限设计(转载)
来源 :https://blog.csdn.net/rocher88/article/details/43190743 这是我在网上找的一些设计比较好的RBAC权限管理 不知道,像新浪.搜狐.网易.百 ...
-
黄聪:保持web页面生成的app一直处于用户登录状态不退出
用户登录了会员中心,怎么保持登录状态! 由于封壳的内核及组件肯定没有浏览器APP应用那么强大,所以目前暂时的解决方案是: jquery.cookie.js 本文转载至:https://www.cnb ...
-
js 变量提升(JavaScript Scoping and Hoisting)
原文网址:http://www.cnblogs.com/betarabbit/archive/2012/01/28/2330446.html 这是一篇作者翻译过来的文章,未翻译的原文网址在这里:htt ...